Ctrl K

Слить соседей ради малого OR

Сложная
Дан массив неотрицательных целых чисел values и число merges. За одну операцию можно взять два **соседних** элемента и заменить их одним — их побитовым AND (&). Длина массива при этом уменьшается на 1. Сделав не больше merges операций, добейтесь того, чтобы побитовое OR всех оставшихся элементов было как можно меньше. Верните это значение.
Пример 1
values=[12, 10, 3, 1], merges=2 → 1

Сольём первые три числа: 12 AND 10 = 8, затем 8 AND 3 = 0. Остаётся [0, 1], их OR равен 1. Получить 0 нельзя: кусок с последней единицей пришлось бы слить с 3, 10 и 12, а это уже 3 операции.

Пример 2
values=[7, 7, 7], merges=2 → 7

AND одинаковых чисел ничего не меняет, так что ответ 7 при любых слияниях.

Пример 3
values=[5, 2, 6, 1], merges=1 → 7
Ограничения
  • 1 ≤ len(values) ≤ 10⁵
  • 0 ≤ values[i] < 2³⁰
  • 0 ≤ merges < len(values)
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиРазмен монет под точную сумму СложнаяПерекладывание битов ради квадратов СложнаяПереключения по рёбрам дерева СложнаяМаксимум двоичных строк после переворотов СредняяКомпании по четыре в кинозале Средняя
загружаем Python…
Вход
values=[12, 10, 3, 1], merges=2
Ожидается
1

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 105 тестов на сервере, включая скрытые.