Description#
You are given a 2D integer array coordinates and an integer k, where coordinates[i] = [xi, yi] are the coordinates of the ith point in a 2D plane.
We define the distance between two points (x1, y1) and (x2, y2) as (x1 XOR x2) + (y1 XOR y2) where XOR is the bitwise XOR operation.
Return the number of pairs (i, j) such that i < j and the distance between points i and j is equal to k.
Example 1:
Input: coordinates = [[1,2],[4,2],[1,3],[5,2]], k = 5
Output: 2
Explanation: 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.
Example 2:
Input: coordinates = [[1,3],[1,3],[1,3],[1,3],[1,3]], k = 0
Output: 10
Explanation: Any two chosen pairs will have a distance of 0. There are 10 ways to choose two pairs.
Constraints:
2 <= coordinates.length <= 500000 <= xi, yi <= 1060 <= k <= 100
Solutions#
Solution 1: Hash Table + Enumeration#
We can use a hash table $cnt$ to count the occurrence of each point in the array $coordinates$.
Next, we enumerate each point $(x_2, y_2)$ in the array $coordinates$. Since the range of $k$ is $[0, 100]$, and the result of $x_1 \oplus x_2$ or $y_1 \oplus y_2$ is always greater than or equal to $0$, we can enumerate the result $a$ of $x_1 \oplus x_2$ in the range $[0,..k]$. Then, the result of $y_1 \oplus y_2$ is $b = k - a$. In this way, we can calculate the values of $x_1$ and $y_1$, and add the occurrence of $(x_1, y_1)$ to the answer.
The time complexity is $O(n \times k)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array $coordinates$.
1
2
3
4
5
6
7
8
9
10
11
| class Solution:
def countPairs(self, coordinates: List[List[int]], k: int) -> int:
cnt = Counter()
ans = 0
for x2, y2 in coordinates:
for a in range(k + 1):
b = k - a
x1, y1 = a ^ x2, b ^ y2
ans += cnt[(x1, y1)]
cnt[(x2, y2)] += 1
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int countPairs(List<List<Integer>> coordinates, int k) {
Map<List<Integer>, Integer> cnt = new HashMap<>();
int ans = 0;
for (var c : coordinates) {
int x2 = c.get(0), y2 = c.get(1);
for (int a = 0; a <= k; ++a) {
int b = k - a;
int x1 = a ^ x2, y1 = b ^ y2;
ans += cnt.getOrDefault(List.of(x1, y1), 0);
}
cnt.merge(c, 1, Integer::sum);
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int countPairs(vector<vector<int>>& coordinates, int k) {
map<pair<int, int>, int> cnt;
int ans = 0;
for (auto& c : coordinates) {
int x2 = c[0], y2 = c[1];
for (int a = 0; a <= k; ++a) {
int b = k - a;
int x1 = a ^ x2, y1 = b ^ y2;
ans += cnt[{x1, y1}];
}
++cnt[{x2, y2}];
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| func countPairs(coordinates [][]int, k int) (ans int) {
cnt := map[[2]int]int{}
for _, c := range coordinates {
x2, y2 := c[0], c[1]
for a := 0; a <= k; a++ {
b := k - a
x1, y1 := a^x2, b^y2
ans += cnt[[2]int{x1, y1}]
}
cnt[[2]int{x2, y2}]++
}
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| function countPairs(coordinates: number[][], k: number): number {
const cnt: Map<number, number> = new Map();
const f = (x: number, y: number): number => x * 1000000 + y;
let ans = 0;
for (const [x2, y2] of coordinates) {
for (let a = 0; a <= k; ++a) {
const b = k - a;
const [x1, y1] = [a ^ x2, b ^ y2];
ans += cnt.get(f(x1, y1)) ?? 0;
}
cnt.set(f(x2, y2), (cnt.get(f(x2, y2)) ?? 0) + 1);
}
return ans;
}
|
Solution 2#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
int countPairs(vector<vector<int>>& coordinates, int k) {
unordered_map<long long, int> cnt;
auto f = [](int x, int y) {
return x * 1000000L + y;
};
int ans = 0;
for (auto& c : coordinates) {
int x2 = c[0], y2 = c[1];
for (int a = 0; a <= k; ++a) {
int b = k - a;
int x1 = a ^ x2, y1 = b ^ y2;
ans += cnt[f(x1, y1)];
}
++cnt[f(x2, y2)];
}
return ans;
}
};
|
