Count Pairs With XOR in a Range Solution in C++

Explore More Solutions

Problem Description

Ah, the classic “Count Pairs With XOR in a Range” problem! It’s like trying to find your socks in a laundry basket—except instead of socks, you’re hunting for pairs of numbers that, when XORed together, fall within a specific range. You know, because who doesn’t love a good number hunt?

Imagine you’re at a party, and you want to find pairs of friends who can dance together without stepping on each other’s toes (or in this case, without their XOR result stepping outside the bounds of low and high). You have a list of dance moves (or numbers), and you need to count how many pairs can dance together without causing a scene.

In simpler terms, given an array of integers and two integers low and high, your task is to count how many pairs (i, j) exist such that i < j and low <= nums[i] XOR nums[j] <= high.

Code Solution


struct TrieNode {
  vector> children;
  int count = 0;
  TrieNode() : children(2) {}
};

class Solution {
 public:
  int countPairs(vector& nums, int low, int high) {
    int ans = 0;

    for (const int num : nums) {
      ans += getCount(num, high + 1) - getCount(num, low);
      insert(num);
    }

    return ans;
  }

 private:
  static constexpr int kHeight = 14;
  shared_ptr root = make_shared();

  void insert(int num) {
    shared_ptr node = root;
    for (int i = kHeight; i >= 0; --i) {
      const int bit = num >> i & 1;
      if (node->children[bit] == nullptr)
        node->children[bit] = make_shared();
      node = node->children[bit];
      ++node->count;
    }
  }

  int getCount(int num, int limit) {
    int count = 0;
    shared_ptr node = root;
    for (int i = kHeight; i >= 0; --i) {
      const int bit = num >> i & 1;
      const int bitLimit = limit >> i & 1;
      if (bitLimit == 1) {
        if (node->children[bit] != nullptr)
          count += node->children[bit]->count;
        node = node->children[bit ^ 1];
      } else {
        node = node->children[bit];
      }
      if (node == nullptr)
        break;
    }
    return count;
  }
};

Approach Explanation

The solution employs a Trie (prefix tree) to efficiently count pairs of numbers that meet the XOR condition. The insert function adds numbers to the Trie while keeping track of how many times each number has been added. The getCount function calculates how many numbers in the Trie yield an XOR result within the specified range when combined with the current number.

By iterating through the list of numbers, the solution counts valid pairs in a single pass, making it both efficient and elegant.

Time and Space Complexity

Time Complexity: O(N * H), where N is the number of elements in nums and H is the height of the Trie (which is constant, given the maximum number of bits for integers).
Space Complexity: O(N * H) in the worst case, due to the storage of Trie nodes.

Real-World Example

Imagine you’re at a trivia night, and you need to form teams based on the XOR of their scores. You want to ensure that the combined scores of each team fall within a certain range to keep the competition fair. This problem is akin to that scenario, where you’re counting how many teams can be formed without exceeding the score limits.