Count pairs with xor in a range

Array Bit Manipulation Trie

46.3% acceptance

Feb 25, 2026

553

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.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_pairs(nums: Vec<i32>, low: i32, high: i32) -> i32 {
    let mut trie: Vec<[i32; 2]> = vec![[-1, -1]];
    let mut cnt: Vec<i32> = vec![0];

    fn trie_insert(trie: &mut Vec<[i32; 2]>, cnt: &mut Vec<i32>, val: i32) {
      let mut node = 0usize;
      for b in (0..=14i32).rev() {
        let bit = ((val >> b) & 1) as usize;
        if trie[node][bit] == -1 {
          let n = trie.len();
          trie.push([-1, -1]);
          cnt.push(0);
          trie[node][bit] = n as i32;
        }
        node = trie[node][bit] as usize;
        cnt[node] += 1;
      }
    }

    fn query_le(trie: &[[i32; 2]], cnt: &[i32], val: i32, limit: i32) -> i32 {
      if limit < 0 { return 0; }
      let mut node = 0usize;
      let mut result = 0i32;
      for b in (0..=14i32).rev() {
        let vb = ((val >> b) & 1) as usize;
        let lb = ((limit >> b) & 1) as usize;
        if lb == 1 {
          let same = vb;
          if trie[node][same] != -1 {
            result += cnt[trie[node][same] as usize];
          }
          let opp = 1 - vb;
          if trie[node][opp] == -1 { return result; }
          node = trie[node][opp] as usize;
        } else {
          let same = vb;
          if trie[node][same] == -1 { return result; }
          node = trie[node][same] as usize;
        }
      }
      result + cnt[node]
    }

    let mut result = 0i32;
    for &num in &nums {
      result += query_le(&trie, &cnt, num, high) - query_le(&trie, &cnt, num, low - 1);
      trie_insert(&mut trie, &mut cnt, num);
    }
    result
  }
}