Задача 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\)

Исходя из этого, для нечётного \(K\) всегда выполняется равенство \((K - 1) \& K = K - 1\).

Так как \(N \geq K\) то мы всегда можем взять \(A = K - 1\) и \(B = K\) и получить максимальный ответ \(K - 1\).

Остался случай с чётным \(K\). Если \(K\) чётное число, то \(K-1\) нечётное, для него можно провести те же самые рассуждения и получить ответ \(K-2\). Но можно ли для чётного \(K\) получить ответ \(K-1\)?

Рассмотрим детальнее числа входящие в выражение \(A \& B\). Будем исходит из того что в ответе задачи получается число \(K-1\), значит либо \(A\), либо \(B\) равно \(K - 1\). Предположим число \(A = K - 1\). Число \(B\) не может быть меньше \(A\), так как должно содержать единицы в тех же позициях что и число \(A\). Чтобы \(B\) отличалось и было минимальным оно должно содержать дополнительную единицу в самом правом разряде в котором в \(A\) содержится 0. Такое число получается при \(B = (K - 1) | K\) (побитовое ИЛИ).

По условию задачи \(A, B \leq N\). \(A = K - 1\) подходит под это условие, а вот \(B = (K - 1) | K\) неизвестно. Пример с числами:

  • \(K = 46_{10} = 101110_2\)
  • \(K - 1 = 45_{10} = 101101_2\)
  • \((K - 1) | K = 101111_2 = 47_{10}\)

При выполнении условия \((K - 1) | K \leq N\) получаем что максимально возможное число в ответе \(K - 1\). Если же условие не выполняется, то ответ будет \(K - 2\).

Причём чётность числа проверять не обязательно. Решение для чётного \(K\) всегда подходит и для нечётного, так как условие \((K - 1) | K \leq N\) всегда выполняется для нечётного \(K \leq N\).

Код решения на Python:

Если вы нашли ошибку, пожалуйста, выделите фрагмент текста и нажмите Ctrl+Enter.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *