*This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful,* *please like**this post and/or* *upvote**my solution post on Leetcode's forums.*

####
Leetcode Problem #970 (*Medium*): Powerful Integers

####
*Description:*

*Description:*

(*Jump to*: *Solution Idea* || *Code*: *JavaScript* | *Python* | *Java* | *C++*)

Given three integers

`x`

,`y`

, and`bound`

,return a list of all the.powerful integersthat have a value less than or equal to`bound`

An integer is

powerfulif 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:*

*Examples:*

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

*Constraints:*

- 1 <= x, y <= 100
- 0 <= bound <= 10^6

####
*Idea:*

*Idea:*

(*Jump to*: *Problem Description* || *Code*: *JavaScript* | *Python* | *Java* | *C++*)

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

*Implementation:*

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

####
*Javascript Code:*

*Javascript Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
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:*

*Python Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
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:*

*Java Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
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:*

*C++ Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
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());
}
};
```

## Top comments (0)