Power of Three

Условие

Дано целое число n. Необходимо определить, является ли оно степенью тройки. Число n является степенью тройки, если существует целое число x такое, что n == 3^x.

Примеры

Input: n = 27

Output: true

Explanation: 27 = 3^3

Input: n = 0

Output: false

Explanation: 0 не может быть степенью тройки.

Input: n = -1

Output: false

Explanation: -1 не может быть степенью тройки.

Решение

fun isPowerOfThree(n: Int): Boolean {
    // Число должно быть больше 0 и делиться на 3 до тех пор, пока не останется 1
    if (n <= 0) return false
    var num = n
    while (num % 3 == 0) {
        num /= 3
    }
    // Если после всех делений num равно 1, значит это степень тройки
    return num == 1
}

Временная сложность

O(log₃(n)) — количество делений на 3 зависит от логарифма числа по основанию 3.

Пространственная сложность

O(1) — используется постоянное количество памяти.