Сложность: medium
Даны три целых числа x, y и bound. Верните список всех мощных чисел, которые имеют значение меньше или равное bound.
Целое число является мощным, если оно может быть представлено как x^i + y^j для некоторых целых чисел i >= 0 и j >= 0.
Вы можете вернуть ответ в любом порядке. В вашем ответе каждое значение должно встречаться не более одного раза.
Пример:
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
👨💻 Алгоритм:
1⃣Вычислите степени a и b как логарифмы bound по основаниям x и y соответственно. Создайте множество powerfulIntegers для хранения результатов.
2⃣Используйте вложенные циклы, где внешний цикл проходит от 0 до a, а внутренний цикл от 0 до b. На каждом шаге вычисляйте x^i + y^j и, если значение меньше или равно bound, добавляйте его в множество powerfulIntegers.
3⃣Используйте вложенные циклы, где внешний цикл проходит от 0 до a, а внутренний цикл от 0 до b. На каждом шаге вычисляйте x^i + y^j и, если значение меньше или равно bound, добавляйте его в множество powerfulIntegers.
😎 Решение:
class Solution:
def powerfulIntegers(self, x, y, bound):
a = bound if x == 1 else int(math.log(bound) / math.log(x))
b = bound if y == 1 else int(math.log(bound) / math.log(y))
powerful_integers = set()
for i in range(a + 1):
for j in range(b + 1):
value = x ** i + y ** j
if value <= bound:
powerful_integers.add(value)
if y == 1: break
if x == 1: break
return list(powerful_integers)
Ставь 👍 и забирай 📚 Базу знаний