Algorithm
Problem Name: 970. Powerful Integers
Problem Link: https://leetcode.com/problems/powerful-integers/
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 <= 1000 <= bound <= 106
Code Examples
#1 Code Example with Python Programming
Code -
Python Programming
class Solution:
def powerfulIntegers(self, x, y, bound):
"""
:type x: int
:type y: int
:type bound: int
:rtype: List[int]
"""
res = set()
i = j = 0
while x ** i <= bound:
while x ** i + y ** j <= bound:
if x ** i + y ** j not in res:
res.add(x ** i + y ** j)
j += 1
if y == 1:
break
j = 0
i += 1
if x == 1:
break
return list(res)
Input
x = 2, y = 3, bound = 10
Output
[2,3,4,5,7,9,10]
#2 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
using System.Linq;
namespace LeetCode
{
public class _0970_PowerfulIntegers
{
public IList < int> PowerfulIntegers(int x, int y, int bound)
{
var results = new HashSet<int>();
for (int i = 1; i < bound; i *= x)
{
for (int j = 1; i + j < = bound; j *= y)
{
results.Add(i + j);
if (y == 1) break;
}
if (x == 1) break;
}
return results.ToArray();
}
}
}
Input
x = 2, y = 3, bound = 10
Output
[2,3,4,5,7,9,10]