Найдите наименьшее значение K такое, что побитовое И чисел в диапазоне [N, NK] равно 0

Для заданного целого числа N задача состоит в том, чтобы найти наименьшее число K такое, что побитовое И всех чисел в диапазоне [N, NK] равно 0, т. е. N & (N - 1) & (N - 2) &... (N – К) = 0 .

Примеры:

Input: N = 17

Output: 2

Explanation:

17&16 = 16

16&15 = 0

Since, we need to find the smallest K, So we stop here.

K = N – 15 = 17 – 15 = 2

Input: N = 4

Output: 1

Explanation:

4&3 = 0

Since, we need to find the smallest k, So we stop here.

Наивный подход: самый простой подход к решению проблемы - начать с заданного числа и взять побитовое И с одним числом меньше текущего числа, пока кумулятивное побитовое И не будет равно 0 . Выполните следующие шаги, чтобы решить эту проблему:

• Объявите переменную cummAnd , в которой хранится коммутативное побитовое И, и инициализируйте ее значением n .
• Объявите переменную i и инициализируйте его с n - 1.
• Запускаем цикл, пока cummAnd не равен 0:
  • cummAnd = cummAnd & i.
  • Уменьшить i на 1.
• Наконец, выведите n – i.

Ниже представлена реализация следующего подхода:

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

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

Эффективный подход: эту проблему можно решить, используя свойства побитового оператора И, т.е. если установлены оба бита, то только результат будет ненулевым. Итак, нам нужно найти наибольшую степень числа 2 , которая меньше или равна N (скажем, X ). Выполните следующие шаги, чтобы решить эту проблему:

• Функция log2(n) дает степень числа 2 , которая равна n .
• Так как его тип возвращаемого значения двойной. Поэтому мы используем функцию пола, чтобы получить наибольшую степень числа 2 , которая меньше или равна n , и сохранить ее в X.
• Х = (1 << Х) – 1.
• Наконец, выведите N – X.

Ниже представлена реализация следующего подхода:

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

Космическая сложность: O(1)