#2857
Count Pairs of Points With Distance k
expert · 1100 · lc medium +32 · verified · 32.8% accepted · 282 likes · top 10%
Description
A 2D integer array coordinates and an integer k are given, where coordinates[i] = [xi, yi].
Define the distance between (x1, y1) and (x2, y2) as (x1 XOR x2) + (y1 XOR y2).
Return the number of pairs (i, j) with i < j whose distance equals exactly 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.
Code
1
2
3