LeetCode-in-Java

2857. Count Pairs of Points With Distance k

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:

• (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

import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution {
    public int countPairs(List<List<Integer>> c, int k) {
        int ans = 0;
        Map<Long, Integer> map = new HashMap<>();
        for (List<Integer> p : c) {
            int p0 = p.get(0);
            int p1 = p.get(1);
            for (int i = 0; i <= k; i++) {
                int x1 = i ^ p0;
                int y1 = (k - i) ^ p1;
                long key2 = hash(x1, y1);
                if (map.containsKey(key2)) {
                    ans += map.get(key2);
                }
            }
            long key = hash(p0, p1);
            map.put(key, map.getOrDefault(key, 0) + 1);
        }
        return ans;
    }

    private long hash(int x1, int y1) {
        long r = (long) 1e8;
        return x1 * r + y1;
    }
}

This site is open source. Improve this page.