Problem Description

Given three integers x, y, and bound, you are to find all powerful integers that can be represented as xi + yj for integers i ≥ 0 and j ≥ 0, such that the result is less than or equal to bound. Each result should be unique (no duplicates), and the output can be in any order.

• x, y, and bound are positive integers.
• Return all possible unique values of xi + yj where i and j are non-negative integers such that the sum is less than or equal to bound.
• Do not include duplicate results.
• There are no restrictions on how many times x or y can be used, except that the powers must remain non-negative and the sum must not exceed bound.

Thought Process

The straightforward way to solve this problem is to try all possible combinations of xi and yj, check if their sum is within bound, and collect these sums. However, if x or y is 1, then repeatedly multiplying will always give 1, so we must be careful to avoid infinite loops or redundant calculations.

Initially, you might consider brute-forcing all possible exponents for x and y up to some high value. But since x and y are positive integers and the result must be less than or equal to bound, the exponents cannot be too large. In fact, we can stop increasing the exponent when xi or yj exceeds bound.

To avoid duplicates, we can use a set to store the results. The challenge is to efficiently and correctly generate all valid pairs (i, j) without missing any or creating duplicates, especially when x or y is 1.

Solution Approach

• Iterate Through Exponents: For each possible exponent i (starting from 0), compute xi as long as it does not exceed bound.
• For each xi, iterate through possible exponents j for y (starting from 0), computing yj as long as the sum xi + yj does not exceed bound.
• Store Results in a Set: Add each valid sum to a set to ensure uniqueness.
• Handle Special Cases: If x or y is 1, then all further powers are also 1, so only the first iteration matters (to avoid infinite loops).
• Return the Results: Convert the set to a list and return it.

This approach ensures that all possible combinations are checked efficiently, and that no duplicates are included in the result.

Example Walkthrough

Let's use x = 2, y = 3, and bound = 10 as an example.

• i = 0: x0 = 1
  • j = 0: 1 + 1 = 2 (add 2)
  • j = 1: 1 + 3 = 4 (add 4)
  • j = 2: 1 + 9 = 10 (add 10)
  • j = 3: 1 + 27 = 28 (exceeds bound, stop)
• i = 1: x1 = 2
  • j = 0: 2 + 1 = 3 (add 3)
  • j = 1: 2 + 3 = 5 (add 5)
  • j = 2: 2 + 9 = 11 (exceeds bound, stop)
• i = 2: x2 = 4
  • j = 0: 4 + 1 = 5 (already in set, skip)
  • j = 1: 4 + 3 = 7 (add 7)
  • j = 2: 4 + 9 = 13 (exceeds bound, stop)
• i = 3: x3 = 8
  • j = 0: 8 + 1 = 9 (add 9)
  • j = 1: 8 + 3 = 11 (exceeds bound, stop)
• i = 4: x4 = 16 (exceeds bound, stop)

The set of unique powerful integers is {2, 3, 4, 5, 7, 9, 10}.

Time and Space Complexity

• Brute-force Approach: If you tried all possible i and j up to large values, the time complexity would be very high (potentially infinite if you don't stop at the bound).
• Optimized Approach: For each exponent, we only go as far as xi ≤ bound and yj ≤ bound. The number of iterations is at most O(\log_x(bound) * \log_y(bound)) since exponents grow exponentially. Using a set, lookups and inserts are O(1) on average.
• Space Complexity: The additional space is O(N) where N is the number of unique powerful integers generated (which is at most bound).

Summary

The key insight is to leverage the exponential growth of powers to limit the number of iterations, and to use a set to ensure uniqueness. By stopping the exponentiation as soon as the values exceed bound, and by handling the special case where x or y is 1, we can efficiently generate all powerful integers without duplicates. This makes the solution both efficient and elegant.

Code Implementation

class Solution:
    def powerfulIntegers(self, x: int, y: int, bound: int) -> list:
        result = set()
        i = 0
        while x ** i <= bound:
            j = 0
            while y ** j <= bound:
                val = x ** i + y ** j
                if val <= bound:
                    result.add(val)
                else:
                    break
                if y == 1:
                    break
                j += 1
            if x == 1:
                break
            i += 1
        return list(result)
    

class Solution {
public:
    vector<int> powerfulIntegers(int x, int y, int bound) {
        unordered_set<int> result;
        for (int i = 0; pow(x, i) <= bound; ++i) {
            for (int j = 0; pow(y, j) <= bound; ++j) {
                int val = pow(x, i) + pow(y, j);
                if (val <= bound)
                    result.insert(val);
                else
                    break;
                if (y == 1)
                    break;
            }
            if (x == 1)
                break;
        }
        return vector<int>(result.begin(), result.end());
    }
};
    

import java.util.*;
class Solution {
    public List<Integer> powerfulIntegers(int x, int y, int bound) {
        Set<Integer> result = new HashSet<>();
        for (int i = 0; Math.pow(x, i) <= bound; ++i) {
            for (int j = 0; Math.pow(y, j) <= bound; ++j) {
                int val = (int)Math.pow(x, i) + (int)Math.pow(y, j);
                if (val <= bound)
                    result.add(val);
                else
                    break;
                if (y == 1)
                    break;
            }
            if (x == 1)
                break;
        }
        return new ArrayList<>(result);
    }
}
    

var powerfulIntegers = function(x, y, bound) {
    const result = new Set();
    let i = 0;
    while (Math.pow(x, i) <= bound) {
        let j = 0;
        while (Math.pow(y, j) <= bound) {
            let val = Math.pow(x, i) + Math.pow(y, j);
            if (val <= bound) {
                result.add(val);
            } else {
                break;
            }
            if (y === 1) break;
            j++;
        }
        if (x === 1) break;
        i++;
    }
    return Array.from(result);
};