# LeetCode 970: Powerful Integers ## Problem Restatement We are given three integers: ```python x y bound ``` An integer is powerful if it can be written as: ```python x ** i + y ** j ``` where: ```python 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 | Item | Meaning | |---|---| | Input | Integers `x`, `y`, and `bound` | | Output | All unique values `x ** i + y ** j <= bound` | | Exponents | `i` and `j` are nonnegative integers | | Order | Any output order is accepted | Example function shape: ```python def powerfulIntegers(x: int, y: int, bound: int) -> list[int]: ... ``` ## Examples Example 1: ```python x = 2 y = 3 bound = 10 ``` Output: ```python [2, 3, 4, 5, 7, 9, 10] ``` Explanation: ```python 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: ```python x = 3 y = 5 bound = 15 ``` Output: ```python [2, 4, 6, 8, 10, 14] ``` ## First Thought: Try Many Exponents The expression has only two independent parts: ```python 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: ```python 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: ```python 1 ``` because: ```python 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: ```python 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: ```python x = 1 ``` then: ```python 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: ```python 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: ```python 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: ```python A = number of powers of x up to bound B = number of powers of y up to bound ``` | Metric | Value | Why | |---|---|---| | Time | `O(A * B)` | We try each bounded power pair | | Space | `O(A * B)` | The set may store many distinct sums | When `x > 1`, `A = O(log_x(bound))`. When `x = 1`, `A = 1`. The same applies to `y`. ## Implementation ```python 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: ```python answer = set() ``` The first power is always: ```python power_x = 1 ``` because any number to the power `0` is `1`. The outer loop enumerates powers of `x`: ```python while power_x <= bound: ``` For each `power_x`, we enumerate powers of `y`: ```python power_y = 1 ``` The inner loop continues only while the sum is valid: ```python while power_x + power_y <= bound: ``` Each valid sum is inserted: ```python answer.add(power_x + power_y) ``` If `y == 1`, multiplying by `y` would not change `power_y`, so we break: ```python if y == 1: break ``` Otherwise, move to the next power: ```python power_y *= y ``` The same logic applies to `x`: ```python if x == 1: break ``` Finally, return the results: ```python return list(answer) ``` ## Testing Because the output order may vary, compare sorted lists. ```python 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: | Test | Why | |---|---| | `(2,3,10)` | Main example | | `(3,5,15)` | Second example | | `(1,2,10)` | Handles `x = 1` | | `(2,1,10)` | Handles `y = 1` | | `(1,1,10)` | Both bases are `1` | | Bound below minimum sum | No valid result | | `(10,10,100)` | Duplicate sums are removed |