Number of alternating xor partitions

Array Hash Table Dynamic Programming Bit Manipulation

26.7% acceptance

Mar 16, 2026

You are given an integer array nums and two distinct integers target1 and target2. A partition is valid if the XOR of elements in its blocks alternates between target1 and target2, starting with target1. Return the number of valid partitions modulo 10^9 + 7.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn alternating_xor(nums: Vec<i32>, target1: i32, target2: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let n = nums.len();

    // prefix XOR
    let mut prefix = vec![0i32; n + 1];
    for i in 0..n {
      prefix[i + 1] = prefix[i] ^ nums[i];
    }

    // dp approach using prefix XOR:
    // dp_odd[i] = ways to partition nums[0..i] into odd number of valid blocks
    // dp_even[i] = ways to partition nums[0..i] into even number of valid blocks
    //
    // For odd blocks (last block target = target1):
    //   prefix[i] ^ prefix[j] == target1 => prefix[j] == prefix[i] ^ target1
    //   where j has even number of blocks before it (or j=0)
    //
    // For even blocks (last block target = target2):
    //   prefix[i] ^ prefix[j] == target2 => prefix[j] == prefix[i] ^ target2
    //   where j has odd number of blocks before it

    use std::collections::HashMap;

    let mut sum_even: HashMap<i32, i64> = HashMap::new();
    let mut sum_odd: HashMap<i32, i64> = HashMap::new();

    // Base: j=0, prefix[0]=0, even (0 blocks)
    *sum_even.entry(0).or_insert(0) += 1;

    let mut answer = 0i64;

    for i in 1..=n {
      let pxor = prefix[i];

      let dp_odd_i = *sum_even.get(&(pxor ^ target1)).unwrap_or(&0) % MOD;
      let dp_even_i = *sum_odd.get(&(pxor ^ target2)).unwrap_or(&0) % MOD;

      *sum_odd.entry(pxor).or_insert(0) += dp_odd_i;
      *sum_odd.entry(pxor).or_insert(0) %= MOD;

      *sum_even.entry(pxor).or_insert(0) += dp_even_i;
      *sum_even.entry(pxor).or_insert(0) %= MOD;

      if i == n {
        answer = (dp_odd_i + dp_even_i) % MOD;
      }
    }

    answer as i32
  }
}