LeetCode 970: Powerful Integers

Problem Restatement

We are given three integers:

x
y
bound

An integer is powerful if it can be written as:

x ** i + y ** j

where:

i >= 0
j >= 0

Return all powerful integers less than or equal to bound.

Each value should appear at most once, and the answer may be returned in any order.

The constraints are 1 <= x, y <= 100 and 0 <= bound <= 10^6.

Input and Output

Example function shape:

def powerfulIntegers(x: int, y: int, bound: int) -> list[int]:
    ...

Examples

Example 1:

x = 2
y = 3
bound = 10

Output:

[2, 3, 4, 5, 7, 9, 10]

Explanation:

2  = 2 ** 0 + 3 ** 0
3  = 2 ** 1 + 3 ** 0
4  = 2 ** 0 + 3 ** 1
5  = 2 ** 1 + 3 ** 1
7  = 2 ** 2 + 3 ** 1
9  = 2 ** 3 + 3 ** 0
10 = 2 ** 0 + 3 ** 2

Example 2:

x = 3
y = 5
bound = 15

Output:

[2, 4, 6, 8, 10, 14]

First Thought: Try Many Exponents

The expression has only two independent parts:

x ** i
y ** j

So we can generate all powers of x that are not too large, all powers of y that are not too large, and combine them.

This is efficient because bound is at most 10^6. Even when the base is 2, the number of powers is small.

For example:

2 ** 20 = 1048576

So there are only about 20 useful powers of 2.

Key Insight

We only need powers whose value is at most bound.

The smallest possible other term is:

1

because:

x ** 0 = 1
y ** 0 = 1

So if one power is already greater than bound, it cannot produce a valid sum.

Use a set to avoid duplicates, because different exponent pairs can produce the same value.

Example:

x = 2
y = 3

2 ** 1 + 3 ** 1 = 5
2 ** 2 + 3 ** 0 = 5

Both produce 5, but the answer should contain 5 once.

Handling x = 1 or y = 1

This is the main edge case.

If:

x = 1

then:

x ** 0 = 1
x ** 1 = 1
x ** 2 = 1
...

The power never changes.

So a loop that repeatedly multiplies by x would never stop.

To avoid this, after processing power 1, break when the base is 1.

The same applies to y.

Algorithm

1. Create an empty set called answer.
2. Start with:

power_x = 1

3. While power_x <= bound:
   • Start with power_y = 1.
   • While power_x + power_y <= bound:
     • Add power_x + power_y to the set.
     • If y == 1, break.
     • Multiply power_y by y.
   • If x == 1, break.
   • Multiply power_x by x.
4. Return the set as a list.

Correctness

Every powerful integer has the form:

x ** i + y ** j

for some i >= 0 and j >= 0.

The outer loop enumerates every possible value of x ** i that can contribute to a valid sum. The inner loop enumerates every possible value of y ** j that can be added to the current x power without exceeding bound.

Whenever the sum is at most bound, the algorithm inserts it into the answer set. Therefore, every generated value is a valid powerful integer.

Conversely, take any valid powerful integer x ** i + y ** j <= bound. Since both terms are positive, x ** i <= bound and y ** j <= bound. The outer loop eventually reaches x ** i, and for that outer value, the inner loop eventually reaches y ** j. So the algorithm adds this valid integer.

The set removes duplicate sums from different exponent pairs. Therefore, the returned list contains exactly the unique powerful integers.

Complexity

Let:

A = number of powers of x up to bound
B = number of powers of y up to bound

When x > 1, A = O(log_x(bound)).

When x = 1, A = 1.

The same applies to y.

Implementation

class Solution:
    def powerfulIntegers(self, x: int, y: int, bound: int) -> list[int]:
        answer = set()

        power_x = 1

        while power_x <= bound:
            power_y = 1

            while power_x + power_y <= bound:
                answer.add(power_x + power_y)

                if y == 1:
                    break

                power_y *= y

            if x == 1:
                break

            power_x *= x

        return list(answer)

Code Explanation

We store unique results in a set:

answer = set()

The first power is always:

power_x = 1

because any number to the power 0 is 1.

The outer loop enumerates powers of x:

while power_x <= bound:

For each power_x, we enumerate powers of y:

power_y = 1

The inner loop continues only while the sum is valid:

while power_x + power_y <= bound:

Each valid sum is inserted:

answer.add(power_x + power_y)

If y == 1, multiplying by y would not change power_y, so we break:

if y == 1:
    break

Otherwise, move to the next power:

power_y *= y

The same logic applies to x:

if x == 1:
    break

Finally, return the results:

return list(answer)

Testing

Because the output order may vary, compare sorted lists.

def run_tests():
    s = Solution()

    assert sorted(s.powerfulIntegers(2, 3, 10)) == [2, 3, 4, 5, 7, 9, 10]
    assert sorted(s.powerfulIntegers(3, 5, 15)) == [2, 4, 6, 8, 10, 14]

    assert sorted(s.powerfulIntegers(1, 2, 10)) == [2, 3, 5, 9]
    assert sorted(s.powerfulIntegers(2, 1, 10)) == [2, 3, 5, 9]
    assert sorted(s.powerfulIntegers(1, 1, 10)) == [2]

    assert sorted(s.powerfulIntegers(2, 3, 1)) == []
    assert sorted(s.powerfulIntegers(10, 10, 100)) == [2, 11, 20]

    print("all tests passed")

run_tests()

Test meaning: