Longest subsequence with non zero bitwise xor

Array Bit Manipulation

37.1% acceptance

Feb 24, 2026

You are given an integer array nums. Return the length of the longest subsequence in nums whose bitwise XOR is non-zero. If no such subsequence exists, return 0.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn longest_subsequence(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    let total_xor: i32 = nums.iter().fold(0, |acc, &x| acc ^ x);
    if total_xor != 0 {
      return n as i32;
    }
    // XOR of all is 0, try removing one element to make it non-zero
    // We need to find an element we can remove to get non-zero XOR
    // XOR after removing element at i = total_xor ^ nums[i] = nums[i] (since total_xor=0)
    // So we need nums[i] != 0
    for i in 0..n {
      if nums[i] != 0 {
        return (n - 1) as i32;
      }
    }
    // All zeros, any subsequence has XOR 0
    0
  }
}