Условие

Дан бинарный массив nums. Мы определяем x_i как число, представляющее собой первые i + 1 элементов массива nums в виде двоичного числа. Требуется вернуть массив булевых значений result, где result[i] равно true, если x_i делится на 5, и false в противном случае.

Примеры

Input: nums = [0, 1, 1] Output: [true, false, false] Explanation: x_0 = 0 (в двоичном виде "0") делится на 5. x_1 = 1 (в двоичном виде "01") не делится на 5. x_2 = 3 (в двоичном виде "011") не делится на 5.

Input: nums = [1, 1, 1] Output: [false, false, false]

Решение

fun prefixesDivBy5(nums: IntArray): List<Boolean> {
    val result = mutableListOf<Boolean>()
    var currentNumber = 0

    for (num in nums) {
        // Сдвигаем текущее число влево на 1 бит и добавляем текущий бит
        currentNumber = (currentNumber shl 1) or num
        // Проверяем, делится ли текущее число на 5
        result.add(currentNumber % 5 == 0)
        // Чтобы избежать переполнения, берем остаток от деления на 5
        currentNumber %= 5
    }

    return result
}

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

O(n), где n — длина массива nums, поскольку мы проходим по массиву один раз.

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

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