Задача: BinaryGap



Задача кодирования BinaryGap - Обучение программированию - Кодирование
Бинарный разрыв в положительном целом числе N - это любая максимальная последовательность последовательных нулей, окруженная единицами в… app.codility.com



Решение:

Алгоритм такой:

1. Сдвинуть вправо 0-й бит, пока не встретится 1-й бит;

2. Пока у нас есть 1-й бит в переменной, сдвигаем все биты вправо и считаем 0-е биты;

3. Каждый раз, когда мы встречаем конец текущего промежутка, устанавливаем его как максимальный промежуток, если он больше, чем предыдущий максимальный промежуток;

4. Вернуть последний максимальный зазор;

Решение не использует дополнительную память, за исключением двух счетчиков, то есть имеет постоянную сложность памяти O (1). Решение выполняет один проход по всем битам, то есть решение имеет временную сложность O (N), где N - количество бит в данной переменной.

Вернитесь к оглавлению.