Powerful Integers

Problem Description

Given three integers x, y, and bound, return a list of all the powerful integers that have a value less than or equal to bound. An integer is powerful if it can be represented as x^i + y^j for some integers i >= 0 and j >= 0. You may return the answer in any order. In your answer, each value should occur at most once.

Key Insights

• A powerful integer is formed by summing powers of two integers x and y.
• We need to consider all combinations of i and j such that the sum does not exceed the given bound.
• We can stop iterating over powers of x and y when their values exceed the bound.
• Use a set to avoid duplicates in the final result.

Space and Time Complexity

Time Complexity: O(log(bound) * log(bound)), where log(bound) is the maximum exponent for x and y. Space Complexity: O(n), where n is the number of unique powerful integers found.

Solution

To solve the problem, we use a nested loop approach:

1. Iterate over powers of x, starting from x^0, until x^i exceeds the bound.
2. For each power of x, iterate over powers of y, starting from y^0, until y^j also exceeds the bound.
3. For each combination of x^i and y^j, calculate the sum and check if it is less than or equal to the bound.
4. Store the results in a set to ensure uniqueness.
5. Finally, convert the set to a list before returning.

Code Solutions