Ctrl K

Пары точек на XOR-расстоянии

Средняя
Дан массив точек points, где points[i] = [x, y], и число k. Расстояние между точками (x1, y1) и (x2, y2) определим необычно: (x1 XOR x2) + (y1 XOR y2), где XOR — побитовое исключающее ИЛИ. Верните количество пар индексов i < j, для которых расстояние между точками i и j равно ровно k. Точки могут повторяться.
Пример 1
points=[[2, 3], [6, 3], [2, 1], [7, 2]], k=4 → 1

Подходит только пара точек 0 и 1: (2 XOR 6) + (3 XOR 3) = 4 + 0 = 4.

Пример 2
points=[[0, 0], [1, 0], [0, 1], [1, 1]], k=1 → 4

Расстояние 1 у точек, отличающихся ровно в одной координате на единицу: (0, 1), (0, 2), (1, 3), (2, 3) — четыре пары.

Пример 3
points=[[4, 4], [4, 4], [4, 4]], k=0 → 3

Все три точки совпадают, любая из трёх пар даёт расстояние 0.

Ограничения
  • 2 ≤ len(points) ≤ 5·10⁴
  • 0 ≤ x, y ≤ 10⁶
  • 0 ≤ k ≤ 100
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиСамая непохожая пара СредняяВсе неубывающие подпоследовательности СредняяВосемь фонарей через много ночей СредняяПалиндром после пары правок СредняяКомпании по четыре в кинозале Средняя
загружаем Python…
Вход
points=[[2, 3], [6, 3], [2, 1], [7, 2]], k=4
Ожидается
1

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