We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Pairs of Points With Distance k

Number: 2953

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

We are given a 2D integer array of points, where each point is represented as [x, y]. We are also given an integer k. The distance between two points (x1, y1) and (x2, y2) is defined as (x1 XOR x2) + (y1 XOR y2) (using bitwise XOR). The task is to count the number of pairs (i, j) (with i < j) such that the distance between the corresponding points equals k.

Key Insights

  • XOR is its own inverse; for any numbers a and b, a XOR (a XOR b) = b.
  • For two points (x, y) and (x', y'), if we let dx = x XOR x' and dy = y XOR y', then the distance is simply dx + dy.
  • In order for the distance to equal k, we must have dx + dy = k.
  • There is a limited number of nonnegative pairs (dx, dy) with dx + dy = k (exactly k+1 possibilities), which allows us to “guess” the XOR differences.
  • Instead of checking every pair of points (which leads to O(n²)), we can use a frequency map on unique points and then for each unique point, iterate over all possible (dx, dy) pairs that sum to k.
  • Care must be taken to avoid double counting; a lexicographical ordering of coordinates can be used so that for every candidate pair, we only count when the candidate is “after” the current point, except when the candidate is the same point (which then uses combination formula).

Space and Time Complexity

Time Complexity: O(m * k) where m is the number of unique points and k is at most 101 (since k <= 100). In the worst case, if almost all points are unique, m ≈ n (n up to 50,000), so the worst-case is roughly O(50,000*101) which is acceptable. Space Complexity: O(m) for storing the frequency map.

Solution

We begin by building a frequency map for all the points. For each unique point (x, y) with frequency f, we iterate over all possible (dx, dy) pairs such that dx + dy = k (there are k+1 pairs because dx can range from 0 to k with dy = k - dx). For each (dx, dy), we compute the candidate point as (x XOR dx, y XOR dy). Because XOR is reversible, if a candidate point exists, then the distance from (x,y) to the candidate will indeed be dx+dy = k.

To ensure that each pair is counted only once, we impose an ordering:

  • If the candidate point is the same as (x, y), we add the number of pairs from that single bucket via combination: f*(f-1)//2.
  • Otherwise, we only add the pair if the candidate point is lexicographically larger than (x, y) (i.e. candidate.x > x, or candidate.x == x and candidate.y > y), and add f * frequency(candidate) to the answer.

This approach efficiently computes the count without double counting.

Code Solutions

# Python solution with line-by-line comments

def countPairs(coordinates, k):
    from collections import defaultdict
    # Build frequency map for each coordinate (x, y)
    freq = defaultdict(int)
    for x, y in coordinates:
        freq[(x, y)] += 1

    # Precompute all (dx, dy) pairs such that dx + dy == k
    possible_diffs = []
    for dx in range(k + 1):
        dy = k - dx
        possible_diffs.append((dx, dy))
    
    ans = 0
    # Sort the keys lexicographically to ensure ordering and avoid double counting
    sorted_points = sorted(freq.keys())
    
    for point in sorted_points:
        f = freq[point]
        (x, y) = point
        # Iterate over all possible (dx, dy) with dx+dy=k
        for (dx, dy) in possible_diffs:
            # Compute candidate point using XOR properties: candidate = (x XOR dx, y XOR dy)
            candidate = (x ^ dx, y ^ dy)
            # If candidate exists in frequency map, then these two points have required distance.
            if candidate in freq:
                # To ensure each unordered pair is counted only once, use lexicographical order.
                if candidate == point:
                    # For candidate equal to point, choose 2 out of f points.
                    ans += f * (f - 1) // 2
                elif candidate > point:
                    ans += f * freq[candidate]
    return ans

# Example usage:
coordinates = [[1, 2], [4, 2], [1, 3], [5, 2]]
k = 5
print(countPairs(coordinates, k))  # Expected output: 2
← Back to All Questions