Задача Bitwise AND

В задаче Bitwise AND дано множество чисел \(S = \{1, 2, 3, ..., N\}\), нужно найти два числа \(A\) и \(B\) такие что значение \(A \& B\) (побитовый оператор И) наибольшее, но меньше заданного \(K\). Вывести наибольшее возможное \(A \& B\).

Ограничения:

  • \(2 \leq N \leq 10^3\)
  • \(2 \leq K \leq N\)

Решение

Решение с перебором рабочее, но не проходит по скорости: всего пар \(N * (N - 1)\), сложность получается \(O(n^2)\).

У этой задачи есть решение за константное время. Предположим число \(K\) нечётное. Это значит что в побитовой записи справа у него находится единица:

\(11_{10} = 1011_2\)

Рассмотрим \(K-1\), в двоичной записи все его цифры совпадают с \(K\) кроме последней в которой находится 0:

\(10_{10} = 1010_2\)

Читать далее Задача Bitwise AND