1803. Count Pairs With XOR in a Range

Description

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

 

Solutions

Solution: Trie

• Time complexity: O(nlog(Max(nums, high)))
• Space complexity: O(nlog(Max(nums, high)))

 

JavaScript

/**
 * @param {number[]} nums
 * @param {number} low
 * @param {number} high
 * @return {number}
 */
const countPairs = function (nums, low, high) {
  const trie = new TrieNode();
  const maxNum = Math.max(...nums, high);
  const log = Math.ceil(Math.log2(maxNum));
  let result = 0;

  const insertNum = num => {
    let current = trie;

    for (let index = log; index >= 0; index--) {
      const bit = (num >> index) & 1;

      if (!current.children[bit]) {
        current.children[bit] = new TrieNode();
      }

      current = current.children[bit];
      current.count += 1;
    }
  };

  const getCount = (num, limit) => {
    let count = 0;
    let current = trie;

    for (let index = log; index >= 0; index--) {
      const bit = (num >> index) & 1;
      const limitBit = (limit >> index) & 1;

      if (limitBit) {
        if (current.children[bit]) {
          count += current.children[bit].count;
        }

        current = current.children[bit ^ 1];
      } else {
        current = current.children[bit];
      }

      if (!current) return count;
    }

    return count;
  };

  for (const num of nums) {
    result += getCount(num, high + 1) - getCount(num, low);
    insertNum(num);
  }

  return result;
};

class TrieNode {
  children = [null, null];
  count = 0;
}