Ctrl K

XOR всех перекрёстных пар

Средняя
Даны два массива неотрицательных целых чисел left и right. Составим все пары, в которых одно число взято из left, а другое — из right: каждый элемент left встречается в паре с каждым элементом right ровно один раз. Для каждой пары посчитаем побитовый XOR её чисел. Верните побитовый XOR всех полученных значений. Пар может быть до 10¹⁰, так что перебрать их все не получится — ищите закономерность.
Пример 1
left=[6, 9], right=[4, 1, 7] → 15

Пары дают 6^4=2, 6^1=7, 6^7=1, 9^4=13, 9^1=8, 9^7=14. XOR всех шести чисел: 2^7^1^13^8^14 = 15.

Пример 2
left=[5, 5], right=[3, 12] → 0

Каждое число встречается в парах чётное число раз, поэтому всё взаимно сокращается и получается 0.

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

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