Powerful Integers

Med

#0924Time: O(log_x(bound) * log_y(bound)). While the Big-O notation is the same as the optimized approach, the actual number of operations is higher due to the lack of efficient pruning.Space: O(log_x(bound) + log_y(bound) + N), where N is the number of powerful integers. This is for storing the two lists of powers and the final result set.

Patterns

Math Enumeration

Data structures

Hash Table

Prompt

Given three integers x, y, and bound, return a list of all the powerful integers that have a value less than or equal to bound.

An integer is powerful if it can be represented as xⁱ + y^j for some integers i >= 0 and j >= 0.

You may return the answer in any order. In your answer, each value should occur at most once.

Example 1:

Input: x = 2, y = 3, bound = 10
Output: [2,3,4,5,7,9,10]
Explanation:
2 = 20 + 30
3 = 21 + 30
4 = 20 + 31
5 = 21 + 31
7 = 22 + 31
9 = 23 + 30
10 = 20 + 32

Example 2:

Input: x = 3, y = 5, bound = 15
Output: [2,4,6,8,10,14]

Constraints:

1 <= x, y <= 100
0 <= bound <= 10⁶

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves pre-calculating all possible powers of x and y that are individually less than the bound. It then iterates through every combination of these powers, checks if their sum is within the bound, and adds the valid sums to a result set. This method is straightforward but less efficient as it doesn't stop checking combinations early even when it's clear the sum will be too large.

Algorithm

Initialize a HashSet<Integer> to store the unique powerful integers.
Generate a list of all powers of x that are less than bound. Let's call this xPowers.
Generate a list of all powers of y that are less than bound. Let's call this yPowers.
Use nested loops to iterate through every power powX in xPowers and every power powY in yPowers.
For each pair, calculate the sum = powX + powY.
If sum <= bound, add the sum to the HashSet.
After iterating through all pairs, convert the HashSet to an ArrayList and return it.

Walkthrough

The core idea is to separate the generation of powers from the calculation of their sums. First, we create two lists: one for powers of x (i.e., x^0, x^1, x^2, ...) and one for powers of y (y^0, y^1, y^2, ...), stopping when the power exceeds bound. Then, we use two nested loops to iterate through every pair of powers, one from each list. For each pair (powX, powY), we compute their sum. If the sum is not greater than bound, we add it to a HashSet to ensure all stored values are unique. This approach is exhaustive but fails to use information from the outer loop to optimize the inner loop's work. For example, if x^i is already bound - 1, the inner loop will still check y^j for all j, even though only y^0=1 could potentially produce a valid sum.

1import java.util.ArrayList;2import java.util.HashSet;3import java.util.List;4import java.util.Set;5 6class Solution {7    public List<Integer> powerfulIntegers(int x, int y, int bound) {8        Set<Integer> result = new HashSet<>();9        List<Integer> xPowers = new ArrayList<>();10        for (int i = 1; i < bound; i *= x) {11            xPowers.add(i);12            if (x == 1) break; // Prevent infinite loop if x is 113        }14 15        List<Integer> yPowers = new ArrayList<>();16        for (int i = 1; i < bound; i *= y) {17            yPowers.add(i);18            if (y == 1) break; // Prevent infinite loop if y is 119        }20 21        for (int powX : xPowers) {22            for (int powY : yPowers) {23                int sum = powX + powY;24                if (sum <= bound) {25                    result.add(sum);26                } else {27                    // This break makes it slightly more optimal, but the fundamental28                    // approach of checking all pairs is less efficient than the next approach.29                    if (y > 1) break;30                }31            }32        }33        return new ArrayList<>(result);34    }35}

Complexity

Time

O(log_x(bound) * log_y(bound)). While the Big-O notation is the same as the optimized approach, the actual number of operations is higher due to the lack of efficient pruning.

Space

O(log_x(bound) + log_y(bound) + N), where N is the number of powerful integers. This is for storing the two lists of powers and the final result set.

Trade-offs

Pros

The logic is simple and easy to understand, separating the concerns of generating powers and summing them.

Cons

Performs many unnecessary computations. For a large powX that is close to bound, the inner loop still iterates through all powY, even though the sum will quickly exceed bound.

This approach uses a more efficient brute-force strategy by integrating the sum check directly into the loop conditions. It iterates through powers of x and y simultaneously. For each power of x, it only considers powers of y as long as their sum does not exceed the bound. This dynamic pruning of the search space makes it significantly faster in practice.

Algorithm

Initialize a HashSet<Integer> to store unique results.
Use a for loop to iterate through powers of x. Let the current power be powX. Start with powX = 1 and in each step, update it by powX *= x. The loop continues as long as powX < bound.
Inside this loop, use a nested for loop to iterate through powers of y. Let the current power be powY. Start with powY = 1 and update it by powY *= y.
The crucial optimization is the condition for the inner loop: it continues only as long as powX + powY <= bound.
Inside the inner loop, add the sum powX + powY to the HashSet.
Handle the edge cases where x or y is 1 by breaking out of the respective loop to prevent an infinite loop.
Finally, convert the HashSet to an ArrayList and return it.

Walkthrough

This optimized method avoids pre-calculating and storing all powers. Instead, it generates them on the fly within nested loops. The outer loop generates powers of x (powX), and the inner loop generates powers of y (powY). The key to its efficiency lies in the inner loop's condition: powX + powY <= bound. As powX (from the outer loop) increases, the upper limit for powY in the inner loop effectively decreases, pruning the search space. Once powX + powY exceeds bound for a given powY, we know that any subsequent, larger power of y will also result in a sum exceeding the bound, so we can safely break the inner loop and move to the next powX. This avoids the redundant checks performed by the previous approach. A HashSet is used to store the results to handle duplicates automatically. Special care is taken for x=1 or y=1 to prevent infinite loops.

1import java.util.ArrayList;2import java.util.HashSet;3import java.util.List;4import java.util.Set;5 6class Solution {7    public List<Integer> powerfulIntegers(int x, int y, int bound) {8        Set<Integer> result = new HashSet<>();9        // Use long for powers to prevent overflow before checking against bound10        for (long powX = 1; powX < bound; powX *= x) {11            for (long powY = 1; powX + powY <= bound; powY *= y) {12                result.add((int) (powX + powY));13                if (y == 1) {14                    // If y is 1, powY will always be 1. Break to avoid infinite loop.15                    break;16                }17            }18            if (x == 1) {19                // If x is 1, powX will always be 1. Break to avoid infinite loop.20                break;21            }22        }23        return new ArrayList<>(result);24    }25}

Complexity

Time

O(log_x(bound) * log_y(bound)). This is a tight upper bound. The actual number of operations is much smaller than the first approach because the inner loop's iterations decrease as the outer loop's power value increases.

Space

O(N), where N is the number of unique powerful integers found. This space is used for the result set. In the worst case, N can be up to O(log_x(bound) * log_y(bound)).

Trade-offs

Pros

Highly efficient due to early termination (pruning) of the inner loop.
Minimal memory usage as it doesn't require storing lists of powers.
Performs the minimum necessary calculations.

Cons

The nested loop structure with breaks for edge cases (x=1 or y=1) can be slightly more complex to reason about compared to the first approach.

Solutions

Solution

1class Solution {2public3  List<Integer> powerfulIntegers(int x, int y, int bound) {4    Set<Integer> ans = new HashSet<>();5    for (int a = 1; a <= bound; a *= x) {6      for (int b = 1; a + b <= bound; b *= y) {7        ans.add(a + b);8        if (y == 1) {9          break;10        }11      }12      if (x == 1) {13        break;14      }15    }16    return new ArrayList<>(ans);17  }18}

1/** * @param {number} x * @param {number} y * @param {number} bound * @return {number[]} */ var powerfulIntegers = function ( x , y , bound ) { const ans = new Set (); for ( let a = 1 ; a <= bound ; a *= x ) { for ( let b = 1 ; a + b <= bound ; b *= y ) { ans . add ( a + b ); if ( y === 1 ) { break ; } } if ( x === 1 ) { break ; } } return [... ans ]; };

1class Solution {2public:3  vector<int> powerfulIntegers(int x, int y, int bound) {4    unordered_set<int> ans;5    for (int a = 1; a <= bound; a *= x) {6      for (int b = 1; a + b <= bound; b *= y) {7        ans.insert(a + b);8        if (y == 1) {9          break;10        }11      }12      if (x == 1) {13        break;14      }15    }16    return vector<int>(ans.begin(), ans.end());17  }18};

1class Solution:2    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]: ans = set() a = 1 while a <= bound: b = 1 while a + b <= bound: ans . add(a + b) b *= y if y == 1: break if x == 1: break a *= x return list(ans)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem