Ctrl K

Первое недостижимое OR

Средняя
Дан массив положительных целых чисел values. Число x назовём достижимым, если можно выбрать непустой набор элементов массива (каждый не больше одного раза), побитовое ИЛИ которых равно x. Верните наименьшее положительное целое число, которое недостижимо.
Пример 1
values=[1, 2, 6] → 4

Получаются 1, 2, 3 = 1 | 2, 6 и 7 = 1 | 6. А 4 не получить: единственное число в массиве, где включён бит со значением 4, — это 6, и OR с ним даёт минимум 6.

Пример 2
values=[3, 5] → 1

Уже 1 получить нельзя: в массиве нет единицы, а любое OR не меньше 3.

Пример 3
values=[4, 1, 2, 8, 9] → 16
Ограничения
  • 1 ≤ len(values) ≤ 10⁵
  • 1 ≤ values[i] ≤ 10⁹
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиБери из любой кучки СредняяСамый длинный отрезок с наибольшим AND СредняяXOR всех перекрёстных пар СредняяИЛИ всех сумм подмножеств СредняяДуэль на стирание с XOR Сложная
загружаем Python…
Вход
values=[1, 2, 6]
Ожидается
4

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