Вам задан массив из всех целых чисел из отрезка \([l, r]\) включая границы. Например, если \(l = 2\) и \(r = 5\), массив будет равен \([2, 3, 4, 5]\). Какое наименьшее количество элементов вам нужно из него удалить, чтобы побитовое И массива перестало быть равно нулю?
Побитовое И — бинарная операция, действие которой эквивалентно применению логического И к каждой паре битов, которые стоят на одинаковых позициях в двоичных представлениях чисел.
Примечание
В первом наборе входных данных, массив равен \([1, 2]\). Сначала, побитовое И равно \(0\), так как \(1\ \& \ 2 = 0\). Однако, после удаления \(1\) (или \(2\)), массив станет равен \([2]\) (или \([1]\)), и его побитовое И будет равно \(2\) (или \(1\)). Можно доказать, что этот ответ оптимальный, то есть ответ равен \(1\).
Во втором наборе, массив равен \([2, 3, 4, 5, 6, 7, 8]\). Сначала, побитовое И равно \(0\). Однако после удаления \(4\), \(5\) и \(8\), массив станет равен \([2, 3, 6, 7]\), и его побитовое И будет равно \(2\). Можно доказать, что этот ответ оптимальный, то есть ответ равен \(3\). Заметим, что возможны и другие способы удалить \(3\) элемента.