3702. Longest Subsequence With Non-Zero Bitwise XOR

Problem Overview

Every subsequence XOR is 0 only when every element is 0.

Intuition

Every subsequence XOR is 0 only when every element is 0. Otherwise the answer is almost the full array: if the XOR of all elements is non-zero, length n works; if it is 0, dropping any single non-zero element leaves XOR equal to that element, so length n-1 is always best.

Algorithm

1Compute xor of all nums and whether any element is non-zero.
2If every element is 0, return 0.
3If xor != 0, return n.
4Otherwise return n - 1.

Example Walkthrough

Input: nums = [1, 2, 3]

1.Full XOR is 1^2^3 = 0, and there are non-zero values.
2.Dropping 1 leaves 2^3 = 1 != 0, length 2.
3.No length-3 non-zero-XOR subsequence exists, so answer is 2.

Output: 2

Common Pitfalls

•All zeros is the only case that returns 0 - a single non-zero element already forms a valid subsequence of length 1.
•When full XOR is 0, removing a zero does not help (new XOR stays 0); remove a non-zero element.
•You never need length less than n-1 when a non-zero exists - no deeper search is required.
•n can be 1e5, so any O(n^2) subsequence DP will TLE.

3702.cs

// Approach: XOR of a subsequence is 0 for every choice only when every
// element is 0. Otherwise: if the full-array XOR is non-zero, length n works;
// if it is 0, removing any non-zero element yields XOR equal to that element,
// so length n-1 is always achievable and maximal.
// Complexity: O(n) time and O(1) space.
public class Solution
{
    public int LongestSubsequence(int[] nums)
    {
        int xor = 0;
        bool hasNonZero = false;

        foreach (int x in nums)
        {
            xor ^= x;
            if (x != 0)
                hasNonZero = true;
        }

        if (!hasNonZero)
            return 0;
        return xor != 0 ? nums.Length : nums.Length - 1;
    }
}

Was this solution helpful?