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

Учитывая целое число N, задача состоит в том, чтобы найти максимальное значение K , такое что N & (N-1) & (N-2) & … & (K) = 0. Здесь & представляет побитовый оператор И.

Пример:

Input: N = 5
Output: 3
Explanation: The value of the expression 5 & 4 & 3 = 0. any value greater than 3 (example 4) will not satisfy
our given condition

Input: N =17
Output: 15

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

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

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

Эффективный подход: по некоторым наблюдениям видно, что ответ всегда равен наибольшей степени числа 2, которая меньше или равна (N-1). Итак, наконец, ответ всегда равен 2^K -1, где K — некоторое значение.

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

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