[Codility] Урок-01: BinaryGap

В этом посте представлено решение для нахождения максимального разрыва между двоичными числами. Для доступа к вышеупомянутой проблеме вы можете нажать на следующую ссылку.

Описание задания

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

Например, число 9 имеет двоичное представление 1001 и содержит двоичный пробел длины 2. Число 529 имеет двоичное представление 1000010001 и содержит два двоичных пробела: один длины 4 и один длины 3. Число 20 имеет двоичное представление 10100 и содержит один двоичный пробел длины 1. Число 15 имеет двоичное представление 1111 и не имеет двоичных пробелов. Число 32 имеет двоичное представление 100000 и не имеет двоичных пробелов.

Напишите функцию:

определение решения (N)

который, учитывая положительное целое число N, возвращает длину его самого длинного двоичного промежутка. Функция должна возвращать 0, если N не содержит двоичного пробела.

Например, при N = 1041 функция должна возвращать 5, потому что N имеет двоичное представление 10000010001 и, следовательно, его самый длинный двоичный пробел имеет длину 5. При N = 32 функция должна возвращать 0, поскольку N имеет двоичное представление '100000' и, следовательно, нет бинарных пробелов.

Напишите эффективный алгоритм для следующих предположений:

• N — целое число в диапазоне [1..2,147,483,647].

Авторские права, 2009–2020 гг., принадлежат Codility Limited. Все права защищены. Несанкционированное копирование, публикация или разглашение запрещено.

Ключевой момент

• Найдите максимальный разрыв между 1.
• Если двоичное число состоит только из 1, вы можете напрямую вернуть 0 в качестве максимального промежутка.

Решение (с использованием Python)

def solution(N):
    list_binary = []
    while(True):
        if(N <= 1):
            list_binary.append(N)
            break
        else: 
            list_binary.append(N % 2)
            N = N // 2
            
    max_gap = 0
    for idx, val_binary in enumerate(list_binary):
        if(val_binary == 1): 
            try: max_gap = max(max_gap, \
                list_binary[idx+1:].index(1))
            except: pass
    
    return max_gap

Используйте приведенное выше решение для справки.
Я рекомендую вам написать собственный исходный код.

Связанный пост