Scale Engineer

Count Pairs With XOR in a Range

Hard
#1649Time: O(N^2), where N is the length of the `nums` array. This is because we have nested loops that result in checking every unique pair of elements.Space: O(1), as it only uses a constant amount of extra space for loop variables and the counter.1 company
Patterns
Bit Manipulation
Data structures
ArrayTrie
Companies
Vimeo

Prompt

Given a (0-indexed) integer array nums and two integers low and high, return the number of nice pairs.

A nice pair is a pair (i, j) where 0 <= i < j < nums.length and low <= (nums[i] XOR nums[j]) <= high.

 

Example 1:

Input: nums = [1,4,2,7], low = 2, high = 6
Output: 6
Explanation: All nice pairs (i, j) are as follows:
    - (0, 1): nums[0] XOR nums[1] = 5 
    - (0, 2): nums[0] XOR nums[2] = 3
    - (0, 3): nums[0] XOR nums[3] = 6
    - (1, 2): nums[1] XOR nums[2] = 6
    - (1, 3): nums[1] XOR nums[3] = 3
    - (2, 3): nums[2] XOR nums[3] = 5

Example 2:

Input: nums = [9,8,4,2,1], low = 5, high = 14
Output: 8
Explanation: All nice pairs (i, j) are as follows:
​​​​​    - (0, 2): nums[0] XOR nums[2] = 13
    - (0, 3): nums[0] XOR nums[3] = 11
    - (0, 4): nums[0] XOR nums[4] = 8
    - (1, 2): nums[1] XOR nums[2] = 12
    - (1, 3): nums[1] XOR nums[3] = 10
    - (1, 4): nums[1] XOR nums[4] = 9
    - (2, 3): nums[2] XOR nums[3] = 6
    - (2, 4): nums[2] XOR nums[4] = 5

 

Constraints:

  • 1 <= nums.length <= 2 * 104
  • 1 <= nums[i] <= 2 * 104
  • 1 <= low <= high <= 2 * 104

Approaches

2 approaches with complexity analysis and trade-offs.

The most straightforward approach is to iterate through every possible pair of numbers in the array, calculate their XOR, and check if the result falls within the specified range [low, high]. We maintain a counter which is incremented for each such 'nice pair'.

Algorithm

  • Initialize a counter count to 0.
  • Use a nested loop to iterate through all unique pairs of indices (i, j) where i < j.
  • For each pair, calculate the XOR value: xorValue = nums[i] ^ nums[j].
  • Check if the xorValue is within the range [low, high].
  • If low <= xorValue <= high, increment the count.
  • After iterating through all pairs, return the final count.

Walkthrough

This method involves a brute-force check of all possible pairs (i, j) with 0 <= i < j < nums.length. We use two nested loops to achieve this. The outer loop iterates from i = 0 to n-2 and the inner loop from j = i + 1 to n-1, where n is the size of the nums array. Inside the inner loop, we compute the XOR of nums[i] and nums[j]. If this XOR value is greater than or equal to low and less than or equal to high, we increment our pair counter. While simple, this approach is inefficient for large arrays.

class Solution {    public int countPairs(int[] nums, int low, int high) {        int n = nums.length;        int count = 0;        for (int i = 0; i < n; i++) {            for (int j = i + 1; j < n; j++) {                int xorValue = nums[i] ^ nums[j];                if (xorValue >= low && xorValue <= high) {                    count++;                }            }        }        return count;    }}

Complexity

Time

O(N^2), where N is the length of the `nums` array. This is because we have nested loops that result in checking every unique pair of elements.

Space

O(1), as it only uses a constant amount of extra space for loop variables and the counter.

Trade-offs

Pros

  • Simple to understand and implement.

  • Requires no additional space, making it very memory-efficient.

Cons

  • The quadratic time complexity makes it too slow for the given constraints, leading to a 'Time Limit Exceeded' error on larger test cases.

Solutions

class Trie { private Trie [] children = new Trie [ 2 ]; private int cnt ; public void insert ( int x ) { Trie node = this ; for ( int i = 15 ; i >= 0 ; -- i ) { int v = ( x >> i ) & 1 ; if ( node . children [ v ] == null ) { node . children [ v ] = new Trie (); } node = node . children [ v ]; ++ node . cnt ; } } public int search ( int x , int limit ) { Trie node = this ; int ans = 0 ; for ( int i = 15 ; i >= 0 && node != null ; -- i ) { int v = ( x >> i ) & 1 ; if ((( limit >> i ) & 1 ) == 1 ) { if ( node . children [ v ] != null ) { ans += node . children [ v ]. cnt ; } node = node . children [ v ^ 1 ]; } else { node = node . children [ v ]; } } return ans ; } } class Solution { public int countPairs ( int [] nums , int low , int high ) { Trie trie = new Trie (); int ans = 0 ; for ( int x : nums ) { ans += trie . search ( x , high + 1 ) - trie . search ( x , low ); trie . insert ( x ); } return ans ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem