Задача: 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 {
    fun powerfulIntegers(x: Int, y: Int, bound: Int): List<Int> {
        val a = if (x == 1) bound else (Math.log(bound.toDouble()) / Math.log(x.toDouble())).toInt()
        val b = if (y == 1) bound else (Math.log(bound.toDouble()) / Math.log(y.toDouble())).toInt()
        val powerfulIntegers = mutableSetOf<Int>()

        for (i in 0..a) {
            for (j in 0..b) {
                val value = Math.pow(x.toDouble(), i.toDouble()).toInt() + Math.pow(y.toDouble(), j.toDouble()).toInt()
                if (value <= bound) {
                    powerfulIntegers.add(value)
                }
                if (y == 1) break
            }
            if (x == 1) break
        }

        return powerfulIntegers.toList()
    }
}

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