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 <= 106In #970 Powerful Integers, the goal is to generate all values of the form x^i + y^j that are less than or equal to a given bound. Since powers grow exponentially, the key idea is to enumerate possible powers of x and y instead of checking every integer up to the bound.
Start by generating powers of x and y while they remain within the limit. For each pair of powers, compute their sum and store the result in a hash set to automatically avoid duplicates. Special attention is required when x = 1 or y = 1, since repeated powers would otherwise create infinite loops.
This enumeration approach dramatically reduces the search space because the number of valid powers is limited by logarithmic growth. Using a set ensures uniqueness and efficient insertions. The method combines math reasoning, enumeration, and hash-based deduplication to efficiently collect all valid powerful integers within the bound.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Enumerating powers of x and y with a Hash Set | O(log_x(bound) * log_y(bound)) | O(k) where k is the number of unique results |
codestorywithMIK
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.
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.
1#include <iostream>
2#include <vector>
3#include <unordered_set>
4#include <cmath>
5
6std::vector<int> powerfulIntegers(int x, int y, int bound) {
7 std::unordered_set<int> powerful;
8 for (int i = 0; pow(x, i) <= bound && i < 20; ++i) {
9 for (int j = 0; pow(y, j) <= bound; ++j) {
10 int sum = pow(x, i) + pow(y, j);
11 if (sum <= bound) {
12 powerful.insert(sum);
13 }
14 if (y == 1) break;
15 }
16 if (x == 1) break;
17 }
18 return std::vector<int>(powerful.begin(), powerful.end());
19}This function in C++ also iterates over possible powers of x and y and inserts valid sums into a std::unordered_set to avoid duplicates. It takes advantage of the pow function to compute powers and uses nested loops to generate combinations of i and j. The function returns the set contents as a vector.
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.
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.
1function powerfulIntegers(x, y, bound) {
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, problems like Powerful Integers are common in coding interviews because they test mathematical reasoning, enumeration strategies, and edge-case handling such as dealing with x = 1 or y = 1.
The optimal approach is to enumerate powers of x and y up to the given bound and compute their sums. A hash set is used to store results and automatically remove duplicates. Because powers grow exponentially, only a small number of combinations need to be checked.
A hash set is the most suitable data structure because multiple (i, j) pairs can produce the same sum. Using a set guarantees uniqueness while maintaining efficient insertion and lookup operations during enumeration.
Powers of x and y increase exponentially, so once a power exceeds the bound it will only get larger. Stopping early prevents unnecessary computations and keeps the algorithm efficient.
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.