Maximum xor of subsequences

Array Math Greedy Bit Manipulation

51.3% acceptance

Feb 25, 2026

You are given an integer array nums of length n where each element is a non-negative integer. Select two subsequences of nums (they may be empty and are allowed to overlap), each preserving the original order of elements, and let: X be the bitwise XOR of all elements in the first subsequence. Y be the bitwise XOR of all elements in the second subsequence. Return the maximum possible value of X XOR Y. Note: The XOR of an empty subsequence is 0.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_xor_subsequences(nums: Vec<i32>) -> i32 {
    // X XOR Y where X = XOR of any subset, Y = XOR of any subset.
    // The set of all achievable XOR values for any subsequence is the linear span
    // of nums over GF(2). Since we can pick any two values from this span,
    // max(X XOR Y) = max over all pairs (x, y) in span of x XOR y.
    // But x, y can be chosen independently from the span.
    // x XOR y is also in the span (since span is closed under XOR).
    // So max(X XOR Y) = max element in the span = max achievable XOR of any subset.
    // Build a linear basis and find the maximum element of the span.
    let mut basis: Vec<i32> = Vec::new();
    for &num in &nums {
      let mut v = num;
      for &b in &basis {
        v = v.min(v ^ b);
      }
      if v > 0 {
        basis.push(v);
      }
    }
    // max in span
    let mut max_xor = 0i32;
    for &b in &basis {
      max_xor = max_xor.max(max_xor ^ b);
    }
    max_xor
  }
}