Subarrays with xor at least k

Array Bit Manipulation Trie Prefix Sum

42.9% acceptance

Mar 31, 2026

Given an array of positive integers nums of length n and a non‑negative integer k. Return the number of contiguous subarrays whose bitwise XOR of all elements is greater than or equal to k.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_xor_subarrays(nums: Vec<i32>, k: i32) -> i64 {
    // Trie-based approach on prefix XOR
    // prefix[i] = nums[0] ^ ... ^ nums[i-1], prefix[0] = 0
    // subarray XOR [l..r] = prefix[r+1] ^ prefix[l]
    // Count pairs where prefix[r+1] ^ prefix[l] >= k
    const BITS: usize = 30; // nums[i] up to ~10^9 < 2^30
    let n = nums.len();
    let mut prefix = vec![0i32; n + 1];
    for i in 0..n {
      prefix[i + 1] = prefix[i] ^ nums[i];
    }

    // Trie node: children[0], children[1], count
    let mut trie = vec![[0usize; 2]]; // children indices
    let mut cnt = vec![0i64]; // count at each node
    let mut result: i64 = 0;

    for &p in &prefix {
      // Query first: count values in trie where val ^ p >= k
      let mut node = 0;
      let mut done = false;
      for bit in (0..BITS).rev() {
        let pb = ((p >> bit) & 1) as usize;
        let kb = ((k >> bit) & 1) as usize;
        if kb == 1 {
          // Need XOR bit = 1, so go to child that gives XOR=1
          let need = 1 - pb;
          if trie[node][need] == 0 {
            done = true;
            break;
          }
          node = trie[node][need];
        } else {
          // Going the XOR=1 direction gives strictly greater, count all
          let give1 = 1 - pb;
          if trie[node][give1] != 0 {
            result += cnt[trie[node][give1]];
          }
          // Continue down XOR=0 direction for equality
          let give0 = pb;
          if trie[node][give0] == 0 {
            done = true;
            break;
          }
          node = trie[node][give0];
        }
      }
      if !done {
        result += cnt[node];
      }

      // Insert p into trie
      node = 0;
      for bit in (0..BITS).rev() {
        let b = ((p >> bit) & 1) as usize;
        if trie[node][b] == 0 {
          trie.push([0; 2]);
          cnt.push(0);
          trie[node][b] = trie.len() - 1;
        }
        node = trie[node][b];
        cnt[node] += 1;
      }
    }

    result
  }
}