Point Pairs at XOR Distance

Medium

You are given an array points, where points[i] = [x, y], and an integer k. Define the distance between (x1, y1) and (x2, y2) in an unusual way: (x1 XOR x2) + (y1 XOR y2), where XOR is bitwise exclusive or. Return the number of index pairs i < j such that points i and j are exactly k apart. Points may repeat.

Example 1

points=[[2, 3], [6, 3], [2, 1], [7, 2]], k=4 → 1

Only points 0 and 1 work: (2 XOR 6) + (3 XOR 3) = 4 + 0 = 4.

Example 2

points=[[0, 0], [1, 0], [0, 1], [1, 1]], k=1 → 4

Distance 1 means the points differ by one in exactly one coordinate: (0, 1), (0, 2), (1, 3), (2, 3), four pairs.

Example 3

points=[[4, 4], [4, 4], [4, 4]], k=0 → 3

All three points coincide, so each of the three pairs is at distance 0.

Constraints

2 ≤ len(points) ≤ 5·10⁴
0 ≤ x, y ≤ 10⁶
0 ≤ k ≤ 100

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Array Hash Table

Similar problems

Most Different Pair Medium All Non-Falling Subsequences Medium Eight Lamps After Many Nights Medium Palindrome After a Few Fixes Medium Groups of Four at the Cinema Medium

Input

points=[[2, 3], [6, 3], [2, 1], [7, 2]], k=4

Expected

Run checks the first 3 tests in your browser. Submit checks all 71 tests on the server, hidden ones included.