Ctrl K

Короткое окно с большим OR

Средняя
Дан массив неотрицательных целых чисел masks и число threshold. Для непрерывного непустого отрезка массива посчитаем побитовое OR всех его элементов. Верните длину самого короткого отрезка, у которого это OR не меньше threshold. Если такого отрезка нет, верните -1.
Пример 1
masks=[4, 1, 2, 8], threshold=11 → 3

Одиночные элементы не дотягивают до 11, пары дают 5, 3 и 10. Отрезок [1, 2, 8] даёт 1 | 2 | 8 = 11 — длина 3.

Пример 2
masks=[1, 2, 1], threshold=4 → -1

Даже OR всего массива равен 3 < 4, подходящего окна нет.

Пример 3
masks=[0, 3], threshold=0 → 1

Порог 0 достигает любое окно, достаточно одного элемента.

Ограничения
  • 1 ≤ len(masks) ≤ 2 · 10⁵
  • 0 ≤ masks[i] ≤ 10⁹
  • 0 ≤ threshold ≤ 10⁹
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиОкно без конфликтующих флагов СредняяКратчайший отрезок с полным OR СредняяГирлянда из трёх ламп СредняяЗажечь все лампы окном СложнаяXOR близкой пары Лёгкая
загружаем Python…
Вход
masks=[4, 1, 2, 8], threshold=11
Ожидается
3

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