Ctrl K

XOR от всех попарных AND

Сложная
Даны два массива неотрицательных целых чисел: first и second. Для каждой пары (i, j), где i — индекс в first, а j — индекс в second, вычислите first[i] AND second[j] (побитовое И). Получится len(first) · len(second) чисел. Верните побитовый XOR всех этих чисел. Прямой перебор пар при длинах до 10⁵ слишком долгий — поищите способ быстрее.
Пример 1
first=[5, 3], second=[6] → 6

5 AND 6 = 4, 3 AND 6 = 2, а 4 XOR 2 = 6.

Пример 2
first=[7], second=[1, 2, 4] → 7

Пары дают 1, 2 и 4; 1 XOR 2 XOR 4 = 7.

Пример 3
first=[8, 8], second=[15] → 0

Обе пары дают 8, а 8 XOR 8 = 0.

Ограничения
  • 1 ≤ len(first), len(second) ≤ 10⁵
  • 0 ≤ first[i], second[j] ≤ 10⁹
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиШахматка перестановками строк и столбцов СложнаяДве группы с одинаковым средним СложнаяДуэль на стирание с XOR СложнаяЦепочки с квадратными суммами СложнаяПроизведение различных простых Сложная
загружаем Python…
Вход
first=[5, 3], second=[6]
Ожидается
6

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