Input: coordinates =[[1,2],[4,2],[1,3],[5,2]], k =5Output: 2Explanation: We can choose the following pairs:-(0,1): Because we have(1 XOR 4)+(2 XOR 2)=5.-(2,3): Because we have(1 XOR 5)+(3 XOR 2)=5.
Input: coordinates =[[1,3],[1,3],[1,3],[1,3],[1,3]], k =0Output: 10Explanation: Any two chosen pairs will have a distance of 0. There are 10 ways to choose two pairs.
For each point, the distance to another point is defined as (x1 XOR x2) + (y1 XOR y2) = k. We can use a hash map to count how many points can form a valid pair with each point by iterating over all possible (dx, dy) such that dx + dy = k, and checking if (x ^ dx, y ^ dy) exists.
classSolution {
public:int countPairs(vector<vector<int>>& coordinates, int k) {
unordered_map<longlong, int> mp;
for (auto& p : coordinates) mp[((longlong)p[0]<<32)|p[1]]++;
int ans =0;
for (auto& p : coordinates) {
mp[((longlong)p[0]<<32)|p[1]]--;
for (int dx =0; dx <= k; ++dx) {
int dy = k - dx;
int x2 = p[0] ^ dx, y2 = p[1] ^ dy;
longlong key = ((longlong)x2<<32)|y2;
if (mp.count(key)) ans += mp[key];
}
}
return ans;
}
};
classSolution {
publicintcountPairs(int[][] coordinates, int k) {
Map<Long, Integer> mp =new HashMap<>();
for (int[] p : coordinates) mp.put(((long)p[0]<<32)|p[1], mp.getOrDefault(((long)p[0]<<32)|p[1], 0)+1);
int ans = 0;
for (int[] p : coordinates) {
mp.put(((long)p[0]<<32)|p[1], mp.get(((long)p[0]<<32)|p[1])-1);
for (int dx = 0; dx <= k; dx++) {
int dy = k - dx;
int x2 = p[0]^dx, y2 = p[1]^dy;
long key = ((long)x2<<32)|y2;
ans += mp.getOrDefault(key, 0);
}
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
classSolution {
funcountPairs(coordinates: Array<IntArray>, k: Int): Int {
val mp = mutableMapOf<Pair<Int,Int>, Int>()
for (p in coordinates) mp[p[0] to p[1]] = mp.getOrDefault(p[0] to p[1], 0) + 1var ans = 0for (p in coordinates) {
mp[p[0] to p[1]] = mp[p[0] to p[1]]!! - 1for (dx in0..k) {
val dy = k - dx
val x2 = p[0] xor dx
val y2 = p[1] xor dy
ans += mp.getOrDefault(x2 to y2, 0)
}
}
return ans
}
}
1
2
3
4
5
6
7
8
9
10
11
12
classSolution:
defcountPairs(self, coordinates: list[list[int]], k: int) -> int:
from collections import Counter
mp = Counter((x, y) for x, y in coordinates)
ans =0for x, y in coordinates:
mp[(x, y)] -=1for dx in range(k+1):
dy = k - dx
x2, y2 = x ^ dx, y ^ dy
ans += mp[(x2, y2)]
return ans
impl Solution {
pubfncount_pairs(coordinates: Vec<Vec<i32>>, k: i32) -> i32 {
use std::collections::HashMap;
letmut mp = HashMap::new();
for p in&coordinates {
*mp.entry((p[0], p[1])).or_insert(0) +=1;
}
letmut ans =0;
for p in&coordinates {
*mp.get_mut(&(p[0], p[1])).unwrap() -=1;
for dx in0..=k {
let dy = k - dx;
let x2 = p[0] ^ dx;
let y2 = p[1] ^ dy;
ans +=*mp.get(&(x2, y2)).unwrap_or(&0);
}
}
ans
}
}