Powerful Integers: Enumerating Sums of Powers

LeetCode Powerful Integers (Problem 970) asks you to find all integers that can be represented as x^i + y^j for some non-negative integers i and j, where the result is at most bound.

At first glance, you might worry about iterating over infinitely many values of i and j. But powers grow fast, so there are only a handful of valid exponents before you blow past the bound.

The problem

Given three integers x, y, and bound, return a list of all the unique values x^i + y^j where those sums are at most bound. You can return the answer in any order.

For example, with x=2, y=3, and bound=10, the valid sums are {2, 3, 4, 5, 7, 9, 10}.

The approach

The key observation is that powers of any base greater than 1 grow exponentially. For x=2, the powers are 1, 2, 4, 8, 16, 32, ... and they exceed any reasonable bound within about log2(bound) steps. That means the number of valid exponents for i is at most log_x(bound), and similarly for j.

The plan is simple:

1. Generate all powers of x that do not exceed bound: these are x^0, x^1, x^2, ...
2. Generate all powers of y the same way.
3. For every pair (x^i, y^j), compute their sum. If the sum is at most bound, add it to a set.
4. Return the set as a list.

A set handles deduplication for free. Different pairs can produce the same sum (for instance, 2+3 = 5 and 4+1 = 5), and you only want each value once.

Step-by-step walkthrough

Let's trace through the algorithm with x=2, y=3, and bound=10.

The code

def powerfulIntegers(x, y, bound):
    result = set()
    xi = 1
    while xi <= bound:
        yj = 1
        while xi + yj <= bound:
            result.add(xi + yj)
            if y == 1:
                break
            yj *= y
        if x == 1:
            break
        xi *= x
    return list(result)

The outer loop walks through powers of x, starting at x^0 = 1. The inner loop walks through powers of y for each fixed x^i. When xi + yj exceeds bound, the inner loop stops. When xi itself exceeds bound, the outer loop stops.

The if y == 1: break and if x == 1: break guards are critical. If x or y equals 1, then x^i or y^j is always 1 regardless of the exponent. Without the break, you would loop forever because 1 * 1 = 1 never grows past the bound.

Complexity analysis

When x or y equals 1, the corresponding dimension collapses to a single value, so the complexity effectively becomes O(log(bound)) for the other variable. The space comes from the set, which stores at most as many values as there are pairs.

The building blocks

Power enumeration with early termination

The core pattern here is generating a sequence of powers until a condition fails. You start at base^0 = 1 and keep multiplying:

power = 1
while power <= limit:
    # use power
    if base == 1:
        break
    power *= base

This pattern appears whenever you need to enumerate exponential values up to a bound. The base == 1 check is a special case that prevents an infinite loop, since 1^k = 1 for all k.

Using sets for deduplication

When multiple inputs can produce the same output, a set collects unique results without extra bookkeeping:

result = set()
for a in candidates_a:
    for b in candidates_b:
        if is_valid(a, b):
            result.add(compute(a, b))
return list(result)

You see this pattern in problems like Two Sum variants, where different index pairs might yield the same sum. The set guarantees uniqueness with O(1) amortized insertion.

Edge cases

• x = 1 or y = 1: The powers of 1 never grow, so you must break after the first iteration to avoid an infinite loop. When x=1 and y=3 with bound=10, the x side is always 1, and you enumerate 1+1=2, 1+3=4, 1+9=10.
• bound = 0: No sum of two positive values (both at least 1) can be 0 or less, so the result is empty. The smallest possible sum is 1 + 1 = 2.
• x = 1 and y = 1: The only possible sum is 1 + 1 = 2. If bound is at least 2, return [2]. Otherwise, return an empty list.
• Large bound with small bases: With x=2 and bound=1000000, you get about 20 powers. With y=2 as well, that is roughly 400 pairs. Still very fast.

From understanding to recall

You have seen how this problem boils down to two nested loops over logarithmically many values, guarded by an early-termination check for the base-1 edge case. The set handles deduplication.

These are small, composable patterns: power enumeration, early termination, and set-based collection. Each one is simple on its own, but combining them under interview pressure requires practice. Spaced repetition lets you drill each building block until it becomes automatic. When a new problem asks you to enumerate exponential values or deduplicate results, you will not need to re-derive the approach from scratch.

Related posts

• Happy Number - Another problem involving repeated mathematical operations and cycle/termination detection.
• Power of Two - Foundational understanding of powers that applies directly here.
• Count Primes - Another mathematical enumeration problem with bound-based termination.