2857. Count Pairs of Points With Distance k

Problem

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 <= 50000
• 0 <= xi, yi <= 106
• 0 <= k <= 100

Solution (Java)

class Solution {
    public int countPairs(List<List<Integer>> coordinates, int k) {
        Map<Integer, Map<Integer, Integer>> count = new HashMap<>();
        int res = 0;
        for (List<Integer> c : coordinates) {
            int x1 = c.get(0), y1 = c.get(1);
            for (int x = 0; x <= k; x++) {
                int x2 = x1 ^ x, y2 = y1 ^ (k - x);
                if (count.containsKey(x2) && count.get(x2).containsKey(y2))
                    res += count.get(x2).get(y2);
            }
            count.computeIfAbsent(x1, x -> new HashMap<>()).put(y1, count.get(x1).getOrDefault(y1, 0) + 1);
        }
        return res;
    }
}

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).