Powerful Integers — Solution in Python, Java & C++
Powerful Integers solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on hash table and math.
Powerful Integers is a medium coding problem on hash table, math and enumeration, asked in Amazon and Apple interviews.
- Difficulty: Medium
- Topics: Hash Table, Math, Enumeration
- Asked at: Amazon, Apple
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
An integer is powerful for x and y if it can be written as x^i + y^j for some integers i >= 0 and j >= 0.
Return every powerful integer that is less than or equal to bound, each listed once, in increasing order.
Example 1
Input: x = 2, y = 3, bound = 10
Output: [2,3,4,5,7,9,10]
Explanation: 2 = 1+1, 3 = 2+1, 4 = 1+3, 5 = 2+3, 7 = 4+3, 9 = 8+1, 10 = 1+9.
Example 2
Input: x = 3, y = 5, bound = 15
Output: [2,4,6,8,10,14]
Example 3
Input: x = 2, y = 1, bound = 10
Output: [2,3,5,9]
Explanation: Every power of 1 is 1, so the values are 2^i + 1.
Constraints
1 <= x, y <= 1000 <= bound <= 10^6
Hints for Powerful Integers
Hint 1
How many powers of
xare at most 10^6? Forx >= 2, no more than 20.Hint 2
So try every pair of a power of
xand a power ofythat keeps the sum withinbound, and collect the sums in a set (different pairs can give the same sum).Hint 3
Base 1 is the trap:
1^iis always 1, so a loop that multiplies byxuntil it exceeds the bound never ends. Stop after the first power when the base is 1.
How to solve Powerful Integers
There are at most about 20 × 20 candidate sums, so enumerate every pair of powers, de-duplicate with a set, and sort.
Approach
- For
a = 1, x, x^2, …whilea <= bound: - For
b = 1, y, y^2, …whilea + b <= bound, adda + bto a set; ify == 1, stop after the firstb. - If
x == 1, stop after the firsta. - Return the set's values in increasing order.
Why it works
Every powerful integer within the bound is some x^i + y^j with both terms at most bound, and the loops visit every such pair: powers only grow, so once a sum exceeds bound larger exponents cannot help. A base of 1 has a single distinct power, which is why its loop runs once. The set removes sums produced by several pairs, such as 1 + 4 = 4 + 1 when x = y.
Complexity
- Time —
O(log_x(bound) · log_y(bound) · log(answer)) — at most a few hundred sums - Space —
O(number of results)
Pitfalls
- An infinite loop when
xoryis 1. - Duplicates: with
x = y = 2, 3 = 1 + 2 = 2 + 1 must appear once. boundcan be 0 or 1, where the answer is empty (the smallest powerful integer is 2).
Reference solution
Python
from typing import List
def powerfulIntegers(x: int, y: int, bound: int) -> List[int]:
found = set()
a = 1
while a <= bound:
b = 1
while a + b <= bound:
found.add(a + b)
if y == 1:
break
b *= y
if x == 1:
break
a *= x
return sorted(found)Java
public static int[] powerfulIntegers(int x, int y, int bound) {
TreeSet<Integer> found = new TreeSet<>();
for (long a = 1; a <= bound; a *= x) {
for (long b = 1; a + b <= bound; b *= y) {
found.add((int) (a + b));
if (y == 1) break;
}
if (x == 1) break;
}
int[] out = new int[found.size()];
int i = 0;
for (int v : found) out[i++] = v;
return out;
}C++
vector<int> powerfulIntegers(int x, int y, int bound) {
set<int> found;
for (long long a = 1; a <= bound; a *= x) {
for (long long b = 1; a + b <= bound; b *= y) {
found.insert((int)(a + b));
if (y == 1) break;
}
if (x == 1) break;
}
return vector<int>(found.begin(), found.end());
}JavaScript
var powerfulIntegers = function(x, y, bound) {
var found = new Set();
for (var a = 1; a <= bound; a *= x) {
for (var b = 1; a + b <= bound; b *= y) {
found.add(a + b);
if (y === 1) break;
}
if (x === 1) break;
}
return Array.from(found).sort(function(p, q) { return p - q; });
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 439 hash table problems · the whole catalogue
Learn the technique: Hashing: Hash Maps and Hash Sets