LeetCode 970 - Powerful Integers

This problem asks us to generate all integers that can be written in the form: where: - i = 0 - j = 0 - the resulting value is less than or equal to bound The inputs are three integers: - x, the base of the first exponential term - y, the base of the second exponential term -…

leetcodemediumhash-tablemathenumeration

LeetCode Problem 970

Difficulty: 🟡 Medium
Topics: Hash Table, Math, Enumeration

Solution

LeetCode 970 - Powerful Integers

Problem Understanding

This problem asks us to generate all integers that can be written in the form:

$x^i + y^j$

where:

  • i >= 0
  • j >= 0
  • the resulting value is less than or equal to bound

The inputs are three integers:

  • x, the base of the first exponential term
  • y, the base of the second exponential term
  • bound, the maximum allowed value

We must return every distinct integer that satisfies the condition. The order of the returned values does not matter.

The important detail is that exponents begin at zero. Since any number raised to the power 0 equals 1, the smallest possible powerful integer is:

$x^0 + y^0 = 1 + 1 = 2$

This means that if bound < 2, the answer must always be an empty list.

The constraints are relatively small:

  • 1 <= x, y <= 100
  • 0 <= bound <= 10^6

Although the bound can be as large as one million, exponential growth happens very quickly. Even powers of 2 exceed one million after only about 20 multiplications. This observation is the key to an efficient solution.

Several edge cases are important:

  • When x == 1, all powers of x are always 1
  • When y == 1, all powers of y are always 1
  • Duplicate values can occur, so we need a structure that automatically removes duplicates
  • Very small bounds such as 0 or 1 should return an empty list immediately

Approaches

Brute Force Approach

A naive solution would try every possible exponent pair (i, j) within some large range and compute:

$x^i + y^j$

For each computed value, we would check whether it is less than or equal to bound. If it is, we store it.

This approach is correct because it exhaustively checks all possible combinations. However, the difficulty lies in determining how far the exponents should go. Without using the exponential growth insight, a brute-force implementation may test many unnecessary powers.

For example, if we arbitrarily loop exponents from 0 to 1000, the algorithm performs over one million combinations, most of which are useless because the values become far larger than bound.

Optimal Approach

The key observation is that powers grow exponentially. Therefore, the number of relevant powers is actually very small.

For example:

  • 2^20 > 10^6
  • 3^13 > 10^6
  • 10^6 itself only has about 20 meaningful powers for small bases

Instead of trying arbitrary exponents, we can generate powers incrementally until they exceed bound.

We generate all valid powers of x and all valid powers of y, then combine them pairwise. Every valid sum is inserted into a set to avoid duplicates.

Special handling is needed when either base equals 1, because:

$1^i = 1$

for all i.

Without special handling, we would enter an infinite loop while repeatedly multiplying by 1.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(K²) with very large K O(K²) Tries many unnecessary exponent combinations
Optimal O(log(bound)²) O(log(bound)) Uses exponential growth to limit possibilities

Algorithm Walkthrough

  1. Create an empty set to store unique powerful integers.
  2. Generate all valid powers of x that are less than or equal to bound.

Start with 1, which represents x^0. Repeatedly multiply by x until the value exceeds bound.

If x == 1, stop immediately after adding 1, because all future powers are identical. 3. Generate all valid powers of y using the same process. 4. Iterate through every pair of powers.

For each pair (px, py), compute:

$px + py$

If the sum is less than or equal to bound, insert it into the set. 5. Convert the set into a list and return it.

Why it works

The algorithm works because every valid powerful integer must be formed from some power of x and some power of y. The generated power lists contain all possible powers that can contribute to a valid answer because any larger power would exceed bound even before adding the second term. By checking every pair of generated powers, we examine every valid combination exactly once. The set guarantees uniqueness when different exponent pairs produce the same sum.

Python Solution

from typing import List

class Solution:
    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:
        if bound < 2:
            return []

        x_powers = []
        y_powers = []

        value = 1
        while value <= bound:
            x_powers.append(value)

            if x == 1:
                break

            value *= x

        value = 1
        while value <= bound:
            y_powers.append(value)

            if y == 1:
                break

            value *= y

        powerful_numbers = set()

        for px in x_powers:
            for py in y_powers:
                total = px + py

                if total <= bound:
                    powerful_numbers.add(total)

        return list(powerful_numbers)

The implementation begins with an early return for bound < 2. Since the smallest possible powerful integer is 2, no valid answer exists below that threshold.

The next section generates all powers of x. The loop starts at 1, corresponding to x^0. After appending the current power, the algorithm multiplies by x to generate the next power.

The special case for x == 1 is essential. Without it, multiplying by 1 would never change the value, causing an infinite loop.

The same logic is repeated for powers of y.

After both power lists are built, the algorithm checks every pair of powers. Each valid sum is inserted into a set, which automatically removes duplicates.

Finally, the set is converted to a list and returned.

Go Solution

func powerfulIntegers(x int, y int, bound int) []int {
    if bound < 2 {
        return []int{}
    }

    xPowers := []int{}
    yPowers := []int{}

    value := 1
    for value <= bound {
        xPowers = append(xPowers, value)

        if x == 1 {
            break
        }

        value *= x
    }

    value = 1
    for value <= bound {
        yPowers = append(yPowers, value)

        if y == 1 {
            break
        }

        value *= y
    }

    powerfulSet := make(map[int]bool)

    for _, px := range xPowers {
        for _, py := range yPowers {
            total := px + py

            if total <= bound {
                powerfulSet[total] = true
            }
        }
    }

    result := []int{}

    for value := range powerfulSet {
        result = append(result, value)
    }

    return result
}

The Go implementation follows the same structure as the Python solution. Since Go does not have a built-in set type, a map[int]bool is used to simulate a set.

Slices are used for storing powers. The implementation carefully handles the x == 1 and y == 1 cases to avoid infinite loops.

No special integer overflow handling is needed because the constraints ensure values remain safely within Go's integer range.

Worked Examples

Example 1

Input: x = 2, y = 3, bound = 10

First generate powers of 2:

Exponent Value
0 1
1 2
2 4
3 8

Next generate powers of 3:

Exponent Value
0 1
1 3
2 9

Now combine every pair.

px py Sum Valid
1 1 2 Yes
1 3 4 Yes
1 9 10 Yes
2 1 3 Yes
2 3 5 Yes
2 9 11 No
4 1 5 Yes
4 3 7 Yes
4 9 13 No
8 1 9 Yes
8 3 11 No
8 9 17 No

Final set:

{2, 3, 4, 5, 7, 9, 10}

Example 2

Input: x = 3, y = 5, bound = 15

Powers of 3:

[1, 3, 9]

Powers of 5:

[1, 5]

Pair combinations:

px py Sum
1 1 2
1 5 6
3 1 4
3 5 8
9 1 10
9 5 14

Final result:

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

Complexity Analysis

Measure Complexity Explanation
Time O(log(bound)²) Number of powers for each base grows logarithmically
Space O(log(bound)) Stores generated powers and result set

The number of generated powers for a base k is approximately:

$\log_k(bound)$

Since we generate powers for both x and y and check every pair, the total work becomes the product of the two logarithmic counts.

In practice, this is extremely fast because exponential growth sharply limits the number of valid powers.

Test Cases

from typing import List

class Solution:
    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:
        if bound < 2:
            return []

        x_powers = []
        y_powers = []

        value = 1
        while value <= bound:
            x_powers.append(value)

            if x == 1:
                break

            value *= x

        value = 1
        while value <= bound:
            y_powers.append(value)

            if y == 1:
                break

            value *= y

        powerful_numbers = set()

        for px in x_powers:
            for py in y_powers:
                total = px + py

                if total <= bound:
                    powerful_numbers.add(total)

        return list(powerful_numbers)

solution = Solution()

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

assert sorted(solution.powerfulIntegers(1, 1, 2)) == [2]  # both bases are 1
assert sorted(solution.powerfulIntegers(1, 2, 10)) == [2, 3, 5, 9]  # x equals 1
assert sorted(solution.powerfulIntegers(2, 1, 10)) == [2, 3, 5, 9]  # y equals 1

assert sorted(solution.powerfulIntegers(2, 2, 1)) == []  # bound too small
assert sorted(solution.powerfulIntegers(2, 2, 0)) == []  # zero bound

assert sorted(solution.powerfulIntegers(2, 2, 100)) == [2, 3, 5, 9, 17, 33, 65]  # duplicate elimination

assert sorted(solution.powerfulIntegers(100, 100, 1000000)) == [2, 101, 200, 10001, 10100, 20000]  # large powers
Test Why
(2, 3, 10) Validates the main example
(3, 5, 15) Verifies different bases
(1, 1, 2) Tests both bases equal to 1
(1, 2, 10) Ensures infinite loop prevention for x
(2, 1, 10) Ensures infinite loop prevention for y
(2, 2, 1) Tests lower bound edge case
(2, 2, 0) Tests zero bound
(2, 2, 100) Verifies duplicate removal
(100, 100, 1000000) Tests large values and logarithmic behavior

Edge Cases

When bound Is Less Than 2

The smallest possible powerful integer is:

$1 + 1 = 2$

Therefore, if bound is 0 or 1, no valid answers exist. A naive implementation might still attempt to generate powers and combinations unnecessarily. The solution avoids this with an immediate early return.

When x or y Equals 1

This is the most important edge case. Since:

$1^i = 1$

for every exponent i, repeatedly multiplying by 1 never changes the value. A loop that generates powers by multiplication would become infinite. The implementation explicitly checks for this condition and breaks immediately after adding the first power.

Duplicate Powerful Integers

Different exponent pairs can produce the same result. For example:

$2^0 + 2^1 = 3$

and:

$2^1 + 2^0 = 3$

Both generate the same integer. Without duplicate handling, the result list would contain repeated values. The implementation solves this by storing results in a set.

Very Large Bounds

Although bound can be as large as one million, the number of generated powers remains small because exponentials grow rapidly. A naive brute-force solution might waste time exploring huge exponent ranges. The optimized implementation only generates powers that are actually useful, keeping the runtime efficient even at the maximum constraint.