Ctrl K

Наборы с полным OR

Средняя
Дан массив положительных чисел values. Из него можно выбрать любой непустой набор элементов и посчитать побитовое OR выбранных чисел. Среди всех таких наборов найдите наибольшее значение OR и верните, сколько наборов его дают. Наборы различаются позициями выбранных элементов: если два одинаковых числа стоят на разных местах, то наборы с одним и с другим — разные.
Пример 1
values=[4, 2, 6] → 5

Наибольшее возможное OR равно 6. Его дают наборы [6], [4, 2], [4, 6], [2, 6] и [4, 2, 6] — всего 5.

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

Любой непустой набор даёт 9: [9] (первая), [9] (вторая) и [9, 9]. Одинаковые значения на разных позициях считаются разными наборами.

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

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