Pairs With XOR in a Range

Hard

You get an array of positive integers codes and two bounds, low and high. Count the index pairs (i, j) with i < j for which the bitwise exclusive or codes[i] xor codes[j] lies between low and high inclusive. Trying every pair takes O(n²); aim for something faster.

Example 1

codes=[3, 5, 6, 9], low=4, high=10 → 3

3 xor 5 = 6, 3 xor 6 = 5 and 3 xor 9 = 10 are in range; 5 xor 6 = 3, 5 xor 9 = 12 and 6 xor 9 = 15 are not.

Example 2

codes=[7, 7, 7], low=1, high=5 → 0

Equal numbers xor to 0, which is below low.

Constraints

1 ≤ len(codes) ≤ 2·10⁴
1 ≤ codes[i] ≤ 2·10⁴
1 ≤ low ≤ high ≤ 2·10⁴

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Trie Array

Similar problems

Words That Fit Each Puzzle Hard Best XOR Partner Under a Cap Hard Best XOR Up the Chain of Command Hard Largest XOR of a Close Pair Hard Most Different Pair Medium

Input

codes=[3, 5, 6, 9], low=4, high=10

Expected

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