Powerful Integers
Problem
Given three integers x, y, and bound, return a list of all powerful integers that have a value less than or equal to bound. An integer is powerful if it can be written as xi + yj for some integers i >= 0 and j >= 0. You may return the answer in any order; it must contain no duplicates.
x = 2, y = 3, bound = 10[2, 3, 4, 5, 7, 9, 10]def powerful_integers(x, y, bound):
result = set()
a = 1
while a <= bound:
b = 1
while a + b <= bound:
result.add(a + b)
if y == 1:
break
b *= y
if x == 1:
break
a *= x
return list(result)function powerfulIntegers(x, y, bound) {
const result = new Set();
for (let a = 1; a <= bound; a *= x) {
for (let b = 1; a + b <= bound; b *= y) {
result.add(a + b);
if (y === 1) break;
}
if (x === 1) break;
}
return [...result];
}class Solution {
public List<Integer> powerfulIntegers(int x, int y, int bound) {
Set<Integer> result = new HashSet<>();
for (int a = 1; a <= bound; a *= x) {
for (int b = 1; a + b <= bound; b *= y) {
result.add(a + b);
if (y == 1) break;
}
if (x == 1) break;
}
return new ArrayList<>(result);
}
}vector<int> powerfulIntegers(int x, int y, int bound) {
unordered_set<int> result;
for (int a = 1; a <= bound; a *= x) {
for (int b = 1; a + b <= bound; b *= y) {
result.insert(a + b);
if (y == 1) break;
}
if (x == 1) break;
}
return vector<int>(result.begin(), result.end());
}Explanation
A "powerful integer" is just any sum of one power of x plus one power of y, like x^i + y^j. Since powers grow fast, there are only a handful that stay under bound, so we can simply list them all.
The trick is two nested loops. The outer loop walks a through the powers of x (1, x, x*x, ...) and the inner loop walks b through the powers of y. For each pair we add a + b into a set, which automatically throws away duplicates.
We stop each loop as soon as the sum would exceed bound. There is one special case: if x (or y) is 1, its powers never grow (1, 1, 1, ...), so we break after one step to avoid an infinite loop.
Example: x = 2, y = 3, bound = 10. With a = 1 we get 1+1=2, 1+3=4, 1+9=10. With a = 2 we get 3, 5; with a = 4 we get 7; with a = 8 we get 9. The set ends up as {2,3,4,5,7,9,10}.
Because the powers double (or triple) each step, only a few values fit under the bound, so this stays very fast.