Partition array for maximum xor and and

Array Math Greedy Bit Manipulation Enumeration

17.6% acceptance

Feb 25, 2026

You are given an integer array nums. Partition the array into three (possibly empty) subsequences A, B, and C such that every element of nums belongs to exactly one subsequence. Your goal is to maximize the value of: XOR(A) + AND(B) + XOR(C) where: XOR(arr) denotes the bitwise XOR of all elements in arr. If arr is empty, its value is defined as 0. AND(arr) denotes the bitwise AND of all elements in arr. If arr is empty, its value is defined as 0. Return the maximum value achievable.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn maximize_xor_and_xor(nums: Vec<i32>) -> i64 {
    let n = nums.len();
    let total_mask = (1usize << n) - 1;
    const BITS: usize = 30;

    // Precompute XOR and AND for all subsets in O(2^n)
    let mut xor_val = vec![0i64; 1 << n];
    let mut and_val = vec![0i64; 1 << n];
    for mask in 1usize..=total_mask {
      let bit = mask.trailing_zeros() as usize;
      let prev = mask ^ (1 << bit);
      xor_val[mask] = xor_val[prev] ^ nums[bit] as i64;
      and_val[mask] = if prev == 0 {
        nums[bit] as i64
      } else {
        and_val[prev] & nums[bit] as i64
      };
    }

    // Insert value into GF(2) basis stored as basis[leading_bit] = vector.
    // Returns the reduced value (0 if linearly dependent).
    fn gf2_insert(basis: &mut [i64; BITS], mut v: i64) -> i64 {
      for i in (0..BITS).rev() {
        if v >> i & 1 == 0 { continue; }
        if basis[i] == 0 { basis[i] = v; return v; }
        v ^= basis[i];
      }
      0
    }

    // Maximum value achievable from span of `basis`.
    fn gf2_max(basis: &[i64; BITS]) -> i64 {
      let mut result = 0i64;
      for i in (0..BITS).rev() {
        result = result.max(result ^ basis[i]);
      }
      result
    }

    let full_mask: i64 = (1i64 << BITS) - 1;
    let mut best = 0i64;

    // For each choice of B (mask_b), the complement is A ∪ C.
    // key insight: XOR(A) + XOR(C) = k + 2*(XOR(A) & ~k)
    //   where k = XOR(comp) = xor_val[comp] (fixed for given comp).
    // So we maximize (t & ~k) for t in span(GF2 basis of comp elements),
    // which equals the max of the span of projected vectors t & ~k.
    // Total complexity: O(n * BITS * 2^n)
    for mask_b in 0usize..=total_mask {
      let comp = total_mask & !mask_b;
      let and_b = and_val[mask_b];
      let k = xor_val[comp]; // XOR of all comp elements
      let inv_k = (!k) & full_mask; // bits where k == 0

      // Build GF(2) basis for elements indexed by bits in comp
      let mut basis = [0i64; BITS];
      let mut tmp = comp;
      while tmp != 0 {
        let bit = tmp.trailing_zeros() as usize;
        tmp &= tmp - 1;
        gf2_insert(&mut basis, nums[bit] as i64);
      }

      // Project each basis vector onto inv_k bits and rebuild basis
      let mut proj_basis = [0i64; BITS];
      for i in (0..BITS).rev() {
        if basis[i] != 0 {
          gf2_insert(&mut proj_basis, basis[i] & inv_k);
        }
      }

      // max(t & ~k) for t in span(basis)
      let max_proj = gf2_max(&proj_basis);
      let val = and_b + k + 2 * max_proj;
      if val > best { best = val; }
    }

    best
  }
}