#970

Medium

LeetCode Problem Workspace

Powerful Integers

Find all integers that can be expressed as x^i + y^j up to a given bound using a Hash Table plus Math approach.

Problem Statement

Given three integers x, y, and bound, generate a list of all integers less than or equal to bound that can be written as x raised to the power i plus y raised to the power j for non-negative integers i and j. Each resulting integer must appear at most once in the output list, and order does not matter.

A powerful integer is defined as any integer that can be expressed in the form x^i + y^j for integers i ≥ 0 and j ≥ 0. Return all powerful integers that satisfy the condition bound >= x^i + y^j, using an approach that combines Hash Table storage and careful mathematical iteration to avoid unnecessary computations.

Examples

Example 1

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

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

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]

Example details omitted.

Constraints

1 <= x, y <= 100
0 <= bound <= 106

Solution Approach

Iterate over powers with early stopping

Compute powers of x and y iteratively, stopping as soon as x^i or y^j exceeds the bound. This ensures we do not perform redundant calculations and keeps loops bounded.

Use a Hash Set to avoid duplicates

Store each computed sum x^i + y^j in a Hash Set to automatically eliminate duplicates. This matches the problem requirement that each value occurs at most once.

Combine nested loops with pruning

Use nested loops for i and j, but break inner loops when sums exceed the bound. This approach leverages the enumeration pattern efficiently while minimizing unnecessary iterations.

Complexity Analysis

Metric	Value
Time	Let
Space	O(N \times M)

Time complexity is O(log_bound(x) * log_bound(y)) because we iterate powers of x and y only until the bound is exceeded. Space complexity is O(N * M) where N and M are the number of powers of x and y that fit within the bound, required for storing sums in a Hash Set.

What Interviewers Usually Probe

Focus on pruning loops as soon as x^i + y^j exceeds the bound.
Ensure duplicate sums are not included, highlighting proper Hash Table usage.
Expect clarification on why enumeration combined with mathematical stopping conditions is efficient.

Common Pitfalls or Variants

Common pitfalls

Failing to break loops early, leading to unnecessary computations and potential TLE.
Using a list instead of a Hash Set, which can allow duplicates in the output.
Incorrectly handling the edge case when x or y equals 1, which causes infinite loops if not properly stopped.

Follow-up variants

Return powerful integers in sorted order instead of arbitrary order.
Restrict i and j to a maximum exponent value instead of using bound.
Compute sums modulo a number to avoid large integers and test modular properties.

FAQ

What defines a powerful integer in LeetCode problem 970?

A powerful integer is any number that can be expressed as x^i + y^j for non-negative integers i and j, not exceeding the given bound.

Why is a Hash Table required for Powerful Integers?

Using a Hash Table ensures each computed sum appears only once, preventing duplicates and satisfying the problem constraints.

How do you handle x or y equal to 1?

When x or y equals 1, the exponent loop must stop after the first iteration to avoid infinite repetition, since 1^i = 1 for all i.

What is the time complexity for generating powerful integers?

Time complexity is O(log_bound(x) * log_bound(y)) because loops iterate over powers only until the sum exceeds the bound.

Can the output be in any order?

Yes, the problem allows returning powerful integers in any order as long as each number appears at most once.

terminal

Solution

Solution 1: Hash Table + Enumeration

According to the description of the problem, a powerful integer can be represented as $x^i + y^j$, where $i \geq 0$, $j \geq 0$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    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)

Continue Practicing

#869 reordered power of 2 #963 minimum area rectangle ii #957 prison cells after n days