Ctrl K

Пары с XOR в диапазоне

Сложная
Даны массив положительных чисел codes и границы low и high. Посчитайте пары индексов (i, j), где i < j, для которых побитовое исключающее ИЛИ codes[i] xor codes[j] лежит в отрезке от low до high включительно. Перебор всех пар работает за O(n²) — попробуйте быстрее.
Пример 1
codes=[3, 5, 6, 9], low=4, high=10 → 3

3 xor 5 = 6, 3 xor 6 = 5 и 3 xor 9 = 10 попадают в отрезок; 5 xor 6 = 3, 5 xor 9 = 12 и 6 xor 9 = 15 — нет.

Пример 2
codes=[7, 7, 7], low=1, high=5 → 0

XOR одинаковых чисел равен 0, а он меньше low.

Ограничения
  • 1 ≤ len(codes) ≤ 2·10⁴
  • 1 ≤ codes[i] ≤ 2·10⁴
  • 1 ≤ low ≤ high ≤ 2·10⁴
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиСлова для головоломок СложнаяЛучший XOR-партнёр под потолком СложнаяЛучший XOR по цепочке начальников СложнаяНаибольший XOR близкой пары СложнаяСамая непохожая пара Средняя
загружаем Python…
Вход
codes=[3, 5, 6, 9], low=4, high=10
Ожидается
3

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