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 xi + yj 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.
Example 1:
Input: x = 2, y = 3, bound = 10 Output: [2,3,4,5,7,9,10] Explanation: 2 = 20 + 30 3 = 21 + 30 4 = 20 + 31 5 = 21 + 31 7 = 22 + 31 9 = 23 + 30 10 = 20 + 32
Example 2:
Input: x = 3, y = 5, bound = 15 Output: [2,4,6,8,10,14]
Constraints:
1 <= x, y <= 1000 <= bound <= 106Problem Overview: You are given integers x, y, and bound. A number is considered powerful if it can be written as x^i + y^j where i >= 0 and j >= 0. The task is to generate all unique powerful integers that are less than or equal to bound.
Approach 1: Iterative Power Combination (O(log_x(bound) * log_y(bound)) time, O(k) space)
This approach enumerates all valid powers of x and y whose sum does not exceed bound. Start with x^0 and repeatedly multiply by x until the value exceeds the bound. Do the same for y. For every pair of powers, compute x^i + y^j. If the result is within the bound, store it in a set to avoid duplicates. The key idea is that powers grow exponentially, so the number of iterations is small—roughly log_x(bound) for x and log_y(bound) for y. A hash set guarantees uniqueness and constant-time insertion. This solution relies on simple enumeration and is easy to implement using concepts from math and hash tables.
Approach 2: Optimized Early Termination (O(log_x(bound) * log_y(bound)) time, O(k) space)
This version improves the iteration by handling edge cases where x == 1 or y == 1. If either base is 1, repeated powers do not change the value (e.g., 1^i = 1). Without special handling, the loop would run indefinitely. The optimized solution breaks the loop once the base equals 1 or once the next power exceeds the bound. During enumeration, compute x^i + y^j and insert valid sums into a set. Early termination reduces unnecessary iterations and keeps the implementation safe for edge cases. This technique is a practical optimization when performing enumeration over exponential sequences.
Recommended for interviews: Interviewers typically expect the enumeration strategy with a hash set. Start by explaining that brute-force over all integers up to the bound would be inefficient. Then show that the number of powers of x and y below the bound is logarithmic, making enumeration feasible. Demonstrating the early termination optimization for x == 1 or y == 1 shows attention to edge cases and production-quality thinking.
This approach involves iterating over possible powers of x and y, and calculating their sums while keeping the sum within the bound. We use two nested loops: one to iterate over powers of x and the other to iterate over powers of y. The results are stored in a set to ensure uniqueness.
The function powerful_integers calculates all powerful integers within the given bound. It uses nested loops where the outer loop iterates over powers of x and the inner loop iterates over powers of y. It calculates the sum x^i + y^j and checks if it's within the bound. If so, it adds the sum to a set. This set ensures all elements are unique.
Time Complexity: O(log(bound)^2) since the loops iterate logarithmically with respect to the bound.
Space Complexity: O(n) where n is the number of unique powerful integers within the bound.
In this approach, we optimize the early termination condition by ensuring that we stop iterating as soon as additional powers do not contribute to any new sums within the bound. This prevents unnecessary iterations and computations.
This JavaScript function employs a similar logic to previous approaches but uses multiplicative updates instead of powers for progression through x^i and y^j. It utilizes Set for uniqueness and converts the result to an array for the final output.
JavaScript
Java
Time Complexity: O(log(bound)^2) as it bounds progression over the log of the bound value.
Space Complexity: O(n) where n is the number of unique powerful integers.
According to the description of the problem, a powerful integer can be represented as x^i + y^j, where i geq 0, j geq 0.
The problem requires us to find all powerful integers that do not exceed bound. We notice that the value range of bound does not exceed 10^6, and 2^{20} = 1048576 \gt 10^6. Therefore, if x geq 2, then i is at most 20 to make x^i + y^j leq bound hold. Similarly, if y geq 2, then j is at most 20.
Therefore, we can use double loop to enumerate all possible x^i and y^j, denoted as a and b respectively, and ensure that a + b leq bound, then a + b is a powerful integer. We use a hash table to store all powerful integers that meet the conditions, and finally convert all elements in the hash table into the answer list and return it.
Note that if
x=1ory=1, then the value ofaorbis always equal to1, and the corresponding loop only needs to be executed once to exit.
The time complexity is O(log^2 bound), and the space complexity is O(log^2 bound).
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Approach 1: Iterative Power Combination | Time Complexity: O(log(bound)^2) since the loops iterate logarithmically with respect to the bound. |
| Approach 2: Optimized Early Termination | Time Complexity: O(log(bound)^2) as it bounds progression over the log of the bound value. |
| Hash Table + Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Power Combination | O(log_x(bound) * log_y(bound)) | O(k) | General solution. Straightforward enumeration of powers with a hash set for uniqueness. |
| Optimized Early Termination | O(log_x(bound) * log_y(bound)) | O(k) | Preferred in interviews. Handles edge cases like x=1 or y=1 and avoids unnecessary iterations. |
Powerful Integers | Live Coding with Explanation | Leetcode - 970 • Algorithms Made Easy • 2,328 views views
Watch 9 more video solutions →Practice Powerful Integers with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor