Medium
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:
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 <= 50000
0 <= xi, yi <= 106
0 <= k <= 100
class Solution {
fun countPairs(coordinates: List<List<Int>>, k: Int): Int {
var ans = 0
val map: MutableMap<Long, Int> = HashMap()
for (p in coordinates) {
val p0 = p[0]
val p1 = p[1]
for (i in 0..k) {
val x1 = i xor p0
val y1 = (k - i) xor p1
val key2 = hash(x1, y1)
if (map.containsKey(key2)) {
ans += map[key2]!!
}
}
val key = hash(p0, p1)
map[key] = map.getOrDefault(key, 0) + 1
}
return ans
}
private fun hash(x1: Int, y1: Int): Long {
val r = 1e8.toLong()
return x1 * r + y1
}
}