Solution: Powerful Integers
Tags: algorithms, javascript, java, python
Published: 2021-04-30 08:05:23

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/powerful-integers/discuss/1183595).*

---

#### [Leetcode Problem #970 (*Medium*): Powerful Integers](https://leetcode.com/problems/powerful-integers/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
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**.

---

#### ***Examples:***
>
Example 1:||
|---:|---|
Input:|x = 2, y = 3, bound = 10
Output:|[2,3,4,5,7,9,10]
Explanation:|2 = 20 + 30<br>3 = 21 + 30<br>4 = 20 + 31<br>5 = 21 + 31<br>7 = 22 + 31<br>9 = 23 + 30<br>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^6

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

This problem is a pretty straightforward one. Since we need to return all powerful integers and not just a count of them, there aren't many shortcuts we can take; we'll have to actually come up with the solution iteratively with nested loops.

First, we can use a **set** structure (**ans**) to prevent duplicate answers. Then we can have our nested loops increment the power of the **x** and **y** values while adding the appropriate results to our set.

One somewhat tricky situation occurs when one or more of the values is a **1**, as that power will continue to be **1** forever, regardless of the exponent. To deal with that, we can force each nested loop to **break** after the first iteration if its original value was a **1**.

Once we've iterated over all possible combinations, we can convert **ans** to an array and **return** it.

---

#### ***Implementation:***

There are only minor differences in the code of each language.

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var powerfulIntegers = function(x, y, bound) {
    let ans = new Set()
    for (let xi = 1; xi < bound; xi *= x) {
        for (let yj = 1; xi + yj <= bound; yj *= y) {
            ans.add(xi + yj)
            if (y === 1) break
        }
        if (x === 1) break
    }
    return Array.from(ans)
}
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:
        ans, xi = set(), 1
        while xi < bound:
            yj = 1
            while xi + yj <= bound:
                ans.add(xi + yj)
                if y == 1: break
                yj *= y
            if x == 1: break
            xi *= x
        return list(ans)
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    public List<Integer> powerfulIntegers(int x, int y, int bound) {
        Set<Integer> ans = new HashSet<>();
        for (int xi = 1; xi < bound; xi *= x) {
            for (int yj = 1; xi + yj <= bound; yj *= y) {
                ans.add(xi + yj);
                if (y == 1) break;
            }
            if (x == 1) break;
        }
        return new ArrayList<Integer>(ans);
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    vector<int> powerfulIntegers(int x, int y, int bound) {
        unordered_set<int> ans;
        for (int xi = 1; xi < bound; xi *= x) {
            for (int yj = 1; xi + yj <= bound; yj *= y) {
                ans.insert(xi + yj);
                if (y == 1) break;
            }
            if (x == 1) break;
        }
        return vector<int>(ans.begin(), ans.end());
    }
};
```