Ctrl K

Тройки с нулевым AND

Сложная
Дан массив неотрицательных целых чисел values. Посчитайте, сколько существует упорядоченных троек индексов (i, j, k), для которых values[i] & values[j] & values[k] == 0, где & — побитовое И. Индексы могут совпадать, и тройки, отличающиеся только порядком индексов, считаются разными.
Пример 1
values=[1, 6] → 6

1 & 6 = 0, поэтому подходит любая тройка, где встречаются оба индекса: из 8 троек не подходят только (0, 0, 0) и (1, 1, 1), то есть ответ 6.

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

Любая тройка даёт 7 & 7 & 7 = 7.

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

Единственная тройка (0, 0, 0) даёт 0.

Ограничения
  • 1 ≤ len(values) ≤ 1000
  • 0 ≤ values[i] < 2¹⁶
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиЦепочки с квадратными суммами СложнаяСлова для головоломок СложнаяПогасить все лампы СложнаяЛучший XOR по цепочке начальников СложнаяИмена с обменом первых букв Сложная
загружаем Python…
Вход
values=[1, 6]
Ожидается
6

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