Минимальное количество последовательных целых чисел до N, чье побитовое И равно 0 с N

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

Примеры:

Input: N = 18
Output: 3
Explanation: 
One possible way is to form a sequence of {15, 16, 17, and 18}. The bitwise AND of the given numbers is equal to 0.
Therefore, a minimum of 3 numbers are needed to make the bitwise AND of a sequence of 4 consecutive elements, including 18 to 0.

Input: N = 4
Output: 1
Explanation: 
One possible way is to form a sequence of {4, 3}. The bitwise AND of the given numbers is equal to 0.
Therefore, a minimum of 1 number is needed to make the bitwise AND of a sequence of 2 consecutive elements including 4 to 0.

Наивный подход: самый простой подход состоит в том, чтобы повторять до тех пор, пока N не станет больше 0 , и на каждой итерации проверять, равно ли побитовое И чисел до сих пор 0 или нет. Если нет, то увеличьте количество на 1 .

Временная сложность: O(N)
Вспомогательное пространство: O(1)

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

1. Чтобы сделать побитовое И последовательности, включающей N , равным 0 , необходимо сделать бит MSB числа N равным 0 .
2. Поэтому идея состоит в том, чтобы включить в последовательность все целые числа, большие или равные (2 ^MSB -1) и меньшие N , это даст минимальный счет.

Выполните следующие шаги, чтобы решить проблему:

• Найдите старший значащий бит целого числа N и сохраните его в переменной, скажем, m .
• Тогда максимальное наименьшее значение, которое будет включено, равно (2 ^м -1) .
• Наконец, выведите счет как (N- (2 ^m -1)) .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O (log (N))
Вспомогательное пространство: O(1)