In this guide, you will get 970. Powerful Integers LeetCode Solution with the best time and space complexity. The solution to Powerful Integers problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
Input: x = 3, y = 5, bound = 15
Output: [2,4,6,8,10,14]
Constraints:
1 <= x, y <= 100
0 <= bound <= 106
Complexity Analysis
Time Complexity:
Space Complexity:
970. Powerful Integers LeetCode Solution in C++
class Solution {
public:
vector<int> powerfulIntegers(int x, int y, int bound) {
unordered_set<int> ans;
for (int i = 1; i < bound; i *= x) {
for (int j = 1; i + j <= bound; j *= y) {
ans.insert(i + j);
if (y == 1)
break;
}
if (x == 1)
break;
}
return {ans.begin(), ans.end()};
}
}; /* code provided by PROGIEZ */
970. Powerful Integers LeetCode Solution in Java
class Solution {
public List<Integer> powerfulIntegers(int x, int y, int bound) {
Set<Integer> ans = new HashSet<>();
for (int i = 1; i < bound; i *= x) {
for (int j = 1; i + j <= bound; j *= y) {
ans.add(i + j);
if (y == 1)
break;
}
if (x == 1)
break;
}
return new ArrayList<>(ans);
}
} // code provided by PROGIEZ
970. Powerful Integers LeetCode Solution in Python
class Solution:
def powerfulIntegers(self, x: int, y: int, bound: int) -> list[int]:
xs = {x**i for i in range(20) if x**i < bound}
ys = {y**i for i in range(20) if y**i < bound}
return list({i + j for i in xs for j in ys if i + j <= bound}) # code by PROGIEZ
