Условие

Дано целое число n. Нужно определить, имеет ли его двоичное представление чередующиеся биты, то есть каждый бит отличается от соседнего.

Примеры

Input: n = 5 Output: true Explanation: Двоичное представление числа 5: 101. Биты чередуются.

Input: n = 7 Output: false Explanation: Двоичное представление числа 7: 111. Биты не чередуются.

Input: n = 11 Output: false Explanation: Двоичное представление числа 11: 1011. Биты не чередуются.

Решение

fun hasAlternatingBits(n: Int): Boolean {
    var num = n
    var prevBit = num and 1 // Сохраняем последний бит
    num = num shr 1 // Сдвигаем число вправо
    while (num > 0) {
        val currentBit = num and 1 // Получаем текущий бит
        if (currentBit == prevBit) return false // Если биты одинаковы, возвращаем false
        prevBit = currentBit // Обновляем предыдущий бит
        num = num shr 1 // Сдвигаем число вправо
    }
    return true // Если цикл завершился, биты чередуются
}

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

O(log n), где n — значение числа, так как мы просматриваем каждый бит.

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

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