# Powerful Integers
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/powerful-integers)
Canonical: https://scaleengineer.com/dsa/problems/powerful-integers
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Hash Table
---
## Problem
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 `xi + yj` 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 <= 106`

# Approaches
## Brute Force with Pre-calculated Powers
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.
**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.
**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`.
### Explanation
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.

```java
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public List<Integer> powerfulIntegers(int x, int y, int bound) {
        Set<Integer> result = new HashSet<>();
        List<Integer> xPowers = new ArrayList<>();
        for (int i = 1; i < bound; i *= x) {
            xPowers.add(i);
            if (x == 1) break; // Prevent infinite loop if x is 1
        }

        List<Integer> yPowers = new ArrayList<>();
        for (int i = 1; i < bound; i *= y) {
            yPowers.add(i);
            if (y == 1) break; // Prevent infinite loop if y is 1
        }

        for (int powX : xPowers) {
            for (int powY : yPowers) {
                int sum = powX + powY;
                if (sum <= bound) {
                    result.add(sum);
                } else {
                    // This break makes it slightly more optimal, but the fundamental
                    // approach of checking all pairs is less efficient than the next approach.
                    if (y > 1) break;
                }
            }
        }
        return new ArrayList<>(result);
    }
}
```
### 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.

## Optimized Brute Force with Pruning
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.
**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)).
**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.
### Explanation
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.

```java
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public List<Integer> powerfulIntegers(int x, int y, int bound) {
        Set<Integer> result = new HashSet<>();
        // Use long for powers to prevent overflow before checking against bound
        for (long powX = 1; powX < bound; powX *= x) {
            for (long powY = 1; powX + powY <= bound; powY *= y) {
                result.add((int) (powX + powY));
                if (y == 1) {
                    // If y is 1, powY will always be 1. Break to avoid infinite loop.
                    break;
                }
            }
            if (x == 1) {
                // If x is 1, powX will always be 1. Break to avoid infinite loop.
                break;
            }
        }
        return new ArrayList<>(result);
    }
}
```
### 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.

# Solutions
### Java

```java
class Solution {
public
  List<Integer> powerfulIntegers(int x, int y, int bound) {
    Set<Integer> ans = new HashSet<>();
    for (int a = 1; a <= bound; a *= x) {
      for (int b = 1; a + b <= bound; b *= y) {
        ans.add(a + b);
        if (y == 1) {
          break;
        }
      }
      if (x == 1) {
        break;
      }
    }
    return new ArrayList<>(ans);
  }
}

```

### JavaScript

```javascript
/** * @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 ]; };
```

### CPP

```cpp
class Solution {
public:
  vector<int> powerfulIntegers(int x, int y, int bound) {
    unordered_set<int> ans;
    for (int a = 1; a <= bound; a *= x) {
      for (int b = 1; a + b <= bound; b *= y) {
        ans.insert(a + b);
        if (y == 1) {
          break;
        }
      }
      if (x == 1) {
        break;
      }
    }
    return vector<int>(ans.begin(), ans.end());
  }
};

```

### Python

```python
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)

```