Максимальный набор чисел из первых N натуральных чисел, у которых побитовое И положительно

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

Примеры:

Input: N = 7
Output: 4
Explanation:
The set of numbers from the first N(= 7) natural numbers whose Bitwise AND is positive is {4, 5, 6, 7}, which is of maximum length.

Input: N = 16
Output: 8

Подход: данная проблема может быть решена на основе наблюдения, что 2 ^N и (2 ^N – 1) дают 0 . Следовательно, максимальная длина набора не должна включать в себя как 2 ^N , так и (2 ^N – 1) в одном наборе. Максимальный подмассив с ненулевым значением AND можно найти как:

• Найдите максимальную степень 2, меньшую или равную N , и если N является степенью 2, ответ должен быть N/2 , например, когда N равно 16 , максимальный подмассив с ненулевым значением AND равен 8 .
• В противном случае ответом будет длина между N и наибольшей степенью числа 2, меньше или равная N.

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

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