LeetCode 3702 - Longest Subsequence With Non-Zero Bitwise XOR

LeetCode Problem 3702

Difficulty: 🟡 Medium
Topics: Array, Bit Manipulation

Solution

Problem Understanding

We are given an integer array nums, and we must determine the maximum possible length of a subsequence whose bitwise XOR is not equal to zero.

A subsequence is formed by deleting zero or more elements from the array while preserving the relative order of the remaining elements. Unlike subarrays, subsequences do not need to be contiguous. This means we may choose any subset of indices as long as the original ordering is preserved.

The key operation in this problem is the bitwise XOR. XOR has several useful properties:

• x XOR 0 = x
• x XOR x = 0
• XOR is associative and commutative

The problem asks for the longest subsequence whose final XOR value is non-zero. Since we want the maximum length, we should try to include as many elements as possible.

The constraints are large:

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^9

Since the array can contain up to one hundred thousand elements, any exponential or quadratic approach is infeasible. This strongly suggests that the solution should run in linear time, or close to it.

An important observation is that the XOR of the entire array determines the answer. If the XOR of all elements is already non-zero, then the entire array is a valid subsequence, and its length is clearly maximal.

If the XOR of the entire array equals zero, we cannot use all elements. We must remove at least one element. The question becomes: can we always remove exactly one element and make the XOR non-zero?

Suppose the total XOR is 0. Removing an element x changes the subsequence XOR to:

$$0 \oplus x = x$$

Thus, if any non-zero element exists, removing that single element produces a subsequence with XOR equal to that element, which is non-zero. Therefore, the answer becomes n - 1.

The only impossible case is when every element is zero. Then every possible subsequence also has XOR 0, so the answer is 0.

Important edge cases include arrays of all zeros, arrays of length one, and arrays whose total XOR is zero but contain at least one non-zero value.

Approaches

Brute Force Approach

A brute-force solution would generate every possible subsequence, compute its XOR, and track the maximum length among subsequences with non-zero XOR.

For an array of length n, there are 2^n possible subsequences. For each subsequence, computing the XOR may require up to O(n) work.

This guarantees correctness because every candidate subsequence is examined. However, it is computationally impossible for n = 10^5.

Even for n = 30, the number of subsequences exceeds one billion, making this approach completely impractical.

Optimal Approach

The key insight comes from understanding XOR behavior.

Let totalXor be the XOR of the entire array.

If totalXor != 0, then the entire array itself is already a valid subsequence with non-zero XOR. Since no subsequence can exceed the length of the full array, the answer is simply n.

If totalXor == 0, then the entire array cannot be used. However, removing one element x changes the XOR to:

$$0 \oplus x = x$$

If there exists any non-zero element, removing exactly one such element gives a subsequence of length n - 1 with non-zero XOR.

If all elements are zero, every subsequence has XOR 0, and the answer is 0.

This reduces the problem to a simple linear scan.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n · 2^n)	O(n)	Enumerates every subsequence
Optimal	O(n)	O(1)	Uses XOR properties to derive answer directly

Algorithm Walkthrough

1. Compute the XOR of all elements in nums.

Iterate through the array and continuously XOR each value into a variable called total_xor. At the end of the loop, this variable stores the XOR of the entire array. 2. Check whether the total XOR is non-zero.

If total_xor != 0, then the entire array already satisfies the condition. Since we want the longest subsequence, return len(nums) immediately. 3. Handle the case where total XOR equals zero.

If total_xor == 0, the full array is invalid. 4. Search for a non-zero element.

Iterate through the array again. If any element is non-zero, removing exactly that element leaves a subsequence whose XOR equals that value, which is non-zero.

In this case, return len(nums) - 1. 5. Handle the all-zero case.

If no non-zero element exists, every number is zero. Any XOR of zeros remains zero, meaning no valid subsequence exists. Return 0.

Why it works

The correctness relies on XOR algebra.

If the XOR of all elements is non-zero, using the whole array is obviously optimal because no subsequence can be longer.

If the XOR of all elements is zero, any valid solution must exclude at least one element. Removing a non-zero value x changes the XOR from 0 to x, which is non-zero. Therefore, a subsequence of length n - 1 is always achievable whenever a non-zero element exists, and no longer subsequence can exist because the full array is invalid.

Thus, the algorithm always returns the maximum possible length.

Python Solution

from typing import List

class Solution:
    def longestSubsequence(self, nums: List[int]) -> int:
        total_xor = 0

        for num in nums:
            total_xor ^= num

        if total_xor != 0:
            return len(nums)

        for num in nums:
            if num != 0:
                return len(nums) - 1

        return 0

The implementation closely follows the algorithm.

First, we compute the XOR of the entire array using total_xor ^= num. This efficiently accumulates the XOR value in a single pass.

If the final XOR is non-zero, we immediately return the full array length because the whole array is already valid.

If the total XOR equals zero, we scan the array again looking for any non-zero element. The existence of such an element guarantees that removing it produces a subsequence with non-zero XOR, so we return len(nums) - 1.

If every element is zero, the second loop never finds a non-zero value, and the function returns 0.

Go Solution

func longestSubsequence(nums []int) int {
	totalXor := 0

	for _, num := range nums {
		totalXor ^= num
	}

	if totalXor != 0 {
		return len(nums)
	}

	for _, num := range nums {
		if num != 0 {
			return len(nums) - 1
		}
	}

	return 0
}

The Go implementation is almost identical to the Python version.

The range loop is used to iterate over the slice while computing XOR. Since the constraints fit comfortably inside Go's int type, integer overflow is not a concern.

Go slices naturally handle empty behavior, though this problem guarantees at least one element in the input array.

Worked Examples

Example 1

Input: nums = [1, 2, 3]

Compute the XOR of the entire array.

Step	Current Number	Running XOR
Start	-	0
1	1	1
2	2	3
3	3	0

The total XOR equals 0, so the full array is invalid.

Now search for a non-zero element:

Element	Non-Zero?
1	Yes

Removing 1 leaves [2, 3].

$$2 \oplus 3 = 1$$

The XOR is non-zero, and the subsequence length is 2.

Output: 2

Example 2

Input: nums = [2, 3, 4]

Compute the XOR of the entire array.

Step	Current Number	Running XOR
Start	-	0
1	2	2
2	3	1
3	4	5

The total XOR is 5, which is non-zero.

Therefore, the entire array is already valid.

Subsequence:

$$2 \oplus 3 \oplus 4 = 5$$

Length = 3.

Output: 3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	At most two passes through the array
Space	O(1)	Uses only a few variables

The algorithm performs one pass to compute the total XOR and, in the worst case, another pass to check for a non-zero element. Since each element is processed a constant number of times, the total running time is linear in the array length.

The memory usage remains constant because we only maintain a few integer variables regardless of input size.

Test Cases

sol = Solution()

assert sol.longestSubsequence([1, 2, 3]) == 2  # example where total XOR is zero
assert sol.longestSubsequence([2, 3, 4]) == 3  # example where full array works

assert sol.longestSubsequence([0]) == 0  # single zero
assert sol.longestSubsequence([5]) == 1  # single non-zero

assert sol.longestSubsequence([0, 0, 0]) == 0  # all zeros
assert sol.longestSubsequence([1, 1]) == 1  # total XOR zero, remove one
assert sol.longestSubsequence([4, 4, 2]) == 3  # full array XOR non-zero
assert sol.longestSubsequence([7, 7, 0]) == 2  # remove one non-zero
assert sol.longestSubsequence([1, 2, 3, 0]) == 3  # total XOR zero
assert sol.longestSubsequence([1000000000]) == 1  # large value boundary

assert sol.longestSubsequence([8, 8, 8, 8]) == 3  # repeated values
assert sol.longestSubsequence([0, 5, 0, 0]) == 3  # one non-zero element

Test	Why
[1,2,3]	Validates total XOR zero case
[2,3,4]	Validates full array solution
[0]	Smallest impossible input
[5]	Smallest valid input
[0,0,0]	All-zero edge case
[1,1]	Pair cancellation with XOR zero
[4,4,2]	Entire array XOR non-zero
[7,7,0]	Must remove one element
[1,2,3,0]	Mixed values with zero total XOR
[1000000000]	Large integer boundary
[8,8,8,8]	Repeated identical values
[0,5,0,0]	Single non-zero amid zeros

Edge Cases

All Elements Are Zero

Consider nums = [0, 0, 0].

Every subsequence XOR will remain 0 because XORing zeros never changes the result. A naive implementation might incorrectly return n - 1, but that would still produce XOR 0.

The implementation avoids this bug by explicitly checking for the existence of a non-zero element before returning n - 1.

Single Element Arrays

For nums = [0], the answer must be 0 because the only possible subsequence has XOR 0.

For nums = [5], the answer is 1 because the single element itself produces non-zero XOR.

The implementation naturally handles both cases through the same XOR logic.

Total XOR Equals Zero

Consider nums = [1, 2, 3].

The entire array XOR is zero, so we cannot use all elements. However, removing any non-zero element immediately makes the XOR non-zero.

A common mistake is attempting expensive dynamic programming or subset enumeration. The implementation instead uses the XOR identity:

$$0 \oplus x = x$$

This guarantees that removing exactly one non-zero element is sufficient, producing the optimal length n - 1.