Domain 2MediumMEDIUM

Powerful Integers

LeetCode problem 970: Powerful Integers (medium).

Domain: medium•Updated: 2026-09-05
#Algorithms

Problem Breakdown

We need to find all integers that can be formed as xi+yjx^i + y^j where exponents are non-negative (i≥0,j≥0i \ge 0, j \ge 0) and the resulting sum does not exceed bound. The output must contain unique values.

Inputs:

  • x, y: Integers ≥1\ge 1. These act as bases for exponentiation.
  • bound: Integer limit (≤106\le 10^6).

Outputs:

  • A list of integers representing the powerful numbers found, in any order.

Implicit Constraints & Edge Cases:

  • Infinite Series Risk: If x=1x=1 or y=1y=1, powers do not grow (e.g., 1n=11^n = 1 for all n≥0n \ge 0). We must handle this explicitly to avoid infinite loops, as the value remains constant.
  • Duplicates: Since we are generating numbers via different combinations of exponents (23+342^3 + 3^4 vs another combination), duplicates can occur (e.g., if multiple pairs (i,j)(i,j) yield same sum). A Set is ideal for deduplication before converting to a list.
  • Lower Bound: The smallest possible powerful integer with x,y≥1x, y \ge 1 and exponents ≥0\ge 0 is 10+10=21^0 + 1^0 = 2. If bound < 2, the result should be an empty list (handled naturally by logic).

Intuition

A brute-force approach would iterate through all possible pairs of (i,j)(i, j) until we find a sum exceeding bound. However, since xx and y≥1y \ge 1, powers grow exponentially. This means for any base ≥2\ge 2, the maximum exponent is logarithmic with respect to bound (≈log⁡base(bound)\approx \log_{base}(bound)).

Why Brute Force Fails: If we simply iterate indefinitely without checking termination conditions, cases where x=1x=1 or y=1y=1 cause infinite loops. Even if bounded by value checks, a naive nested loop over exponents is inefficient compared to generating powers directly until they exceed the limit.

Key Insight: We can generate valid terms for x and y independently up to the point where adding them exceeds bound. Since we only care about sums ≤bound\le bound, once xi>boundx^i > bound (or even if it’s small but combined with min(yj=1y^j=1) exceeds), we stop. We use a nested loop structure:

  1. Outer loop generates powers of x (curr_x=x0,x1,…curr\_x = x^0, x^1, \dots). Stop when curr_x>boundcurr\_x > bound. Handle base-1 case to break after one iteration.
  2. Inner loop generates powers of y. For each valid power of x, iterate through all valid powers of y such that sum ≤bound\le bound.

Approach

  1. Initialize a set res to store unique powerful integers found.
  2. Start with curr_x=x0=1curr\_x = x^0 = 1 and enter an outer loop:
    • Check if adding the smallest power of y (1j=11^j=1) exceeds bound. If so, break (optimization). Actually simpler: check if current sum > bound inside inner logic or just iterate powers.
    • To prevent infinite loops when x=1x=1, we must stop generating new terms for x once processed if base is 1.
  3. Inside the outer loop, initialize curr_y=y0=1curr\_y = y^0 = 1 and enter an inner loop:
    • Calculate val = curr_x + curr_y. If val <= bound, add to set.
    • Update curr_y←curr_y∗ycurr\_y \leftarrow curr\_y * y.
    • Break the inner loop if next power exceeds what’s useful (sum > bound) or if base is 1 (value won’t change).
  4. After inner loop, update curr_x←curr_x∗xcurr\_x \leftarrow curr\_x * x.
  5. Check termination for outer loop: break if curr_x grows beyond limit OR if base was 1 and we’ve processed it once.
  6. Convert set to list and return.

Complexity Analysis

  • Time: The number of iterations is proportional to the product of valid exponents, roughly O(log⁡x(bound)×log⁡y(bound))O(\log_x(bound) \times \log_y(bound)). Since bound ≤106\le 10^6, this results in a very small constant (e.g., for base=2, max exponent ~20). Operations inside are O(1).
  • Space: We store unique powerful integers. In the worst case, we might have many distinct sums fitting under bound, but bounded by bound itself (O(bound)O(bound)) and practically much smaller due to exponential growth of terms.

Solution

def powerful_integers(x: int, y: int, bound: int):
    res = set()
    
    # Handle powers of x
    curr_x = 1
    
    while True:
        if curr_x > bound: 
            break
        
        # Inner loop for powers of y
        curr_y = 1
        while True:
            val = curr_x + curr_y
            
            if val <= bound:
                res.add(val)
            
            next_curr_y = curr_y * y
            
            # Break inner loop conditions: 
            # 1. Next power exceeds what's useful (sum will definitely exceed bound since min(y^j)=1 is already checked implicitly via logic, but strictly we check if term itself > bound to prune search space)
            #    Actually simpler: break if next_curr_y > bound OR y==1 (no growth). 
            # 2. If base is 1, value doesn't change -> stop iterating for this loop level immediately after first pass logic? No, we just need to prevent infinite multiplication.
            
            if next_curr_y > bound or (y == 1):
                break
            
            curr_y = next_curr_y
        
        # Update x power
        curr_x *= x
        
        # Break outer loop conditions: 
        # If base is 1, value doesn't change -> stop after first pass to avoid infinite loop.
        if x == 1:
            break

    return list(res)

Edge Cases Handled

  • Base Equals One: Explicitly checks if y == 1 and if x == 1. If a base is 1, the value of powers remains constant (1n=11^n = 1). The code breaks immediately after processing this term to prevent infinite loops while ensuring valid sums are added.
  • Duplicates: Uses a Python set which automatically handles duplicate values generated by different exponent combinations (e.g., 23+30≠4+12^3 + 3^0 \neq 4+1, but theoretically other combos could overlap). Converting back to list at the end satisfies output format.
  • Bound Limitation: Checks val <= bound before adding and breaks loops when terms exceed this limit, ensuring no unnecessary computation or overflow beyond constraints (though Python handles large integers automatically, we prune based on logic).