2857. Count Pairs of Points With Distance k

Problem Statement

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

Intuition

Approach:

Since K constraint is less,
We can iterate throught the k

x1^x2 = i , y1^y2 = k-i
a^b = c -> b = c^a

Go through all k's

Links

https://leetcode.com/problems/count-pairs-of-points-with-distance-k/description/

Video Links

https://www.youtube.com/watch?v=1Hp6Hsghtno&ab_channel=AryanMittal

Approach 1:

C++

class Solution {
public:
    int countPairs(vector<vector<int>>& arr, int k) {
        map<pair<int,int> , int> mp;
        int ans = 0;
        for(auto &it: arr){
            int x1 = it[0], y1 = it[1];
            for(int i=0; i<=k; i++){
                int x2 = x1^i;
                int y2 = y1^(k-i);

                ans += mp[{x2,y2}];
            }

            mp[{x1,y1}]++;
        }

        return ans;
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++

Similar Problems