1803. Count Pairs With XOR in a Range LeetCode Solution

In this guide, you will get 1803. Count Pairs With XOR in a Range LeetCode Solution with the best time and space complexity. The solution to Count Pairs With XOR in a Range problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Count Pairs With XOR in a Range solution in C++
Count Pairs With XOR in a Range solution in Java
Count Pairs With XOR in a Range solution in Python
Additional Resources

1803. Count Pairs With XOR in a Range LeetCode Solution image

Problem Statement of Count Pairs With XOR in a Range

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

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

1803. Count Pairs With XOR in a Range LeetCode Solution in C++

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

class Solution {
 public:
  int countPairs(vector<int>& 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<TrieNode> root = make_shared<TrieNode>();

  void insert(int num) {
    shared_ptr<TrieNode> 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<TrieNode>();
      node = node->children[bit];
      ++node->count;
    }
  }

  // Returns the number of numbers < limit.
  int getCount(int num, int limit) {
    int count = 0;
    shared_ptr<TrieNode> 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;
  }
};
/* code provided by PROGIEZ */

1803. Count Pairs With XOR in a Range LeetCode Solution in Java

class TrieNode {
  public TrieNode[] children = new TrieNode[2];
  public int count = 0;
}

class Solution {
  public int countPairs(int[] nums, int low, int high) {
    int ans = 0;

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

    return ans;
  }

  private final int kHeight = 14;
  private TrieNode root = new TrieNode();

  private void insert(int num) {
    TrieNode node = root;
    for (int i = kHeight; i >= 0; --i) {
      final int bit = num >> i & 1;
      if (node.children[bit] == null)
        node.children[bit] = new TrieNode();
      node = node.children[bit];
      ++node.count;
    }
  }

  // Returns the number of numbers < limit.
  private int getCount(int num, int limit) {
    int count = 0;
    TrieNode node = root;
    for (int i = kHeight; i >= 0; --i) {
      final int bit = num >> i & 1;
      final int bitLimit = ((limit >> i) & 1);
      if (bitLimit == 1) {
        if (node.children[bit] != null)
          count += node.children[bit].count;
        node = node.children[bit ^ 1];
      } else {
        node = node.children[bit];
      }
      if (node == null)
        break;
    }
    return count;
  }
}
// code provided by PROGIEZ