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 thati < j and the distance between pointsi andj is equal tok.

Examples

Example 1

1
2
3
4
5

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

1
2
3

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 <= 10^6
  • 0 <= k <= 100

Solution

Method 1 – Hash Map and Bit Manipulation

Intuition

For each point, the distance to another point is defined as (x1 XOR x2) + (y1 XOR y2) = k. We can use a hash map to count how many points can form a valid pair with each point by iterating over all possible (dx, dy) such that dx + dy = k, and checking if (x ^ dx, y ^ dy) exists.

Approach

  1. Use a hash map to count the frequency of each point.
  2. For each point (x, y):
    1. For all possible (dx, dy) with dx + dy = k and dx, dy >= 0:
      • Compute (x ^ dx, y ^ dy).
      • If this point exists in the map, add its count to the answer.
    2. Decrement the count of (x, y) to avoid double counting.
  3. Return the total number of valid pairs.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int countPairs(vector<vector<int>>& coordinates, int k) {
        unordered_map<long long, int> mp;
        for (auto& p : coordinates) mp[((long long)p[0]<<32)|p[1]]++;
        int ans = 0;
        for (auto& p : coordinates) {
            mp[((long long)p[0]<<32)|p[1]]--;
            for (int dx = 0; dx <= k; ++dx) {
                int dy = k - dx;
                int x2 = p[0] ^ dx, y2 = p[1] ^ dy;
                long long key = ((long long)x2<<32)|y2;
                if (mp.count(key)) ans += mp[key];
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func countPairs(coordinates [][]int, k int) int {
    mp := map[[2]int]int{}
    for _, p := range coordinates {
        mp[[2]int{p[0], p[1]}]++
    }
    ans := 0
    for _, p := range coordinates {
        mp[[2]int{p[0], p[1]}]--
        for dx := 0; dx <= k; dx++ {
            dy := k - dx
            x2, y2 := p[0]^dx, p[1]^dy
            ans += mp[[2]int{x2, y2}]
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int countPairs(int[][] coordinates, int k) {
        Map<Long, Integer> mp = new HashMap<>();
        for (int[] p : coordinates) mp.put(((long)p[0]<<32)|p[1], mp.getOrDefault(((long)p[0]<<32)|p[1], 0)+1);
        int ans = 0;
        for (int[] p : coordinates) {
            mp.put(((long)p[0]<<32)|p[1], mp.get(((long)p[0]<<32)|p[1])-1);
            for (int dx = 0; dx <= k; dx++) {
                int dy = k - dx;
                int x2 = p[0]^dx, y2 = p[1]^dy;
                long key = ((long)x2<<32)|y2;
                ans += mp.getOrDefault(key, 0);
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fun countPairs(coordinates: Array<IntArray>, k: Int): Int {
        val mp = mutableMapOf<Pair<Int,Int>, Int>()
        for (p in coordinates) mp[p[0] to p[1]] = mp.getOrDefault(p[0] to p[1], 0) + 1
        var ans = 0
        for (p in coordinates) {
            mp[p[0] to p[1]] = mp[p[0] to p[1]]!! - 1
            for (dx in 0..k) {
                val dy = k - dx
                val x2 = p[0] xor dx
                val y2 = p[1] xor dy
                ans += mp.getOrDefault(x2 to y2, 0)
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def countPairs(self, coordinates: list[list[int]], k: int) -> int:
        from collections import Counter
        mp = Counter((x, y) for x, y in coordinates)
        ans = 0
        for x, y in coordinates:
            mp[(x, y)] -= 1
            for dx in range(k+1):
                dy = k - dx
                x2, y2 = x ^ dx, y ^ dy
                ans += mp[(x2, y2)]
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

impl Solution {
    pub fn count_pairs(coordinates: Vec<Vec<i32>>, k: i32) -> i32 {
        use std::collections::HashMap;
        let mut mp = HashMap::new();
        for p in &coordinates {
            *mp.entry((p[0], p[1])).or_insert(0) += 1;
        }
        let mut ans = 0;
        for p in &coordinates {
            *mp.get_mut(&(p[0], p[1])).unwrap() -= 1;
            for dx in 0..=k {
                let dy = k - dx;
                let x2 = p[0] ^ dx;
                let y2 = p[1] ^ dy;
                ans += *mp.get(&(x2, y2)).unwrap_or(&0);
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    countPairs(coordinates: number[][], k: number): number {
        const mp: Record<string, number> = {};
        for (const [x, y] of coordinates) {
            const key = `${x},${y}`;
            mp[key] = (mp[key] || 0) + 1;
        }
        let ans = 0;
        for (const [x, y] of coordinates) {
            mp[`${x},${y}`]--;
            for (let dx = 0; dx <= k; dx++) {
                const dy = k - dx;
                const x2 = x ^ dx, y2 = y ^ dy;
                ans += mp[`${x2},${y2}`] || 0;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(nk) where n is the number of points and k is the given distance (since for each point, we check k+1 possible (dx, dy) pairs).
  • 🧺 Space complexity: O(n) for the hash map storing point counts.