Power of Four

Условие

Дано целое число n. Необходимо вернуть true, если n является степенью числа 4. Иначе вернуть false.

Число n является степенью числа 4, если существует целое число x такое, что n == 4^x.

Примеры

Input: n = 16

Output: true

Input: n = 5

Output: false

Input: n = 1

Output: true

Решение

fun isPowerOfFour(n: Int): Boolean {
    // Проверяем, что n больше 0, является степенью 2 и его остаток от деления на 3 равен 1
    return n > 0 && (n and (n - 1)) == 0 && (n % 3 == 1)
}

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

O(1), так как проверка условий выполняется за константное время.

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

O(1), так как не используем дополнительной памяти, кроме нескольких переменных для вычислений.