Ctrl K

ИЛИ всех сумм подмножеств

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

Выбирая любое подмножество, можно получить суммы 0, 1, 2, …, 7. Их побитовое ИЛИ — 7.

Пример 2
values=[8, 8] → 24

Возможные суммы: 0, 8 и 16. 8 | 16 = 24.

Пример 3
values=[0] → 0

Любая сумма равна нулю.

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

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