Задача: 970. Powerful Integers
Сложность: 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 {
    function powerfulIntegers($x, $y, $bound) {
        $a = $x == 1 ? $bound : intval(log($bound) / log($x));
        $b = $y == 1 ? $bound : intval(log($bound) / log($y));
        $powerfulIntegers = [];

        for ($i = 0; $i <= $a; $i++) {
            for ($j = 0; $j <= $b; $j++) {
                $value = pow($x, $i) + pow($y, $j);
                if ($value <= $bound) {
                    $powerfulIntegers[$value] = true;
                }
                if ($y == 1) break;
            }
            if ($x == 1) break;
        }

        return array_keys($powerfulIntegers);
    }
}

Ставь 👍 и забирай 📚 Базу знаний