3702. Longest Subsequence With Non-Zero Bitwise XOR

MediumBit ManipulationArray

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer array nums.

Your task is to find the length of the longest subsequence of nums whose bitwise XOR of all its elements is non-zero.

A subsequence is a sequence derived from the array by deleting some (or no) elements without changing the order of the remaining elements. The subsequence must be non-empty.

If no such subsequence exists (meaning every possible non-empty subsequence has a bitwise XOR equal to zero), return 0.

Key points to understand:

The bitwise XOR of a subsequence is computed by applying the ^ operation across all of its elements. For example, the XOR of [1, 2, 3] is 1 ^ 2 ^ 3 = 0.
You want the subsequence to be as long as possible, while its XOR result is not equal to zero.
Note that if all elements in nums are 0, then any subsequence will have an XOR of 0, so the answer in that case is 0.

Example:

If nums = [1, 2, 3], the XOR of the whole array is 0, but removing one non-zero element (say 3) gives [1, 2] with XOR 3 != 0, so the answer is 2.
If nums = [1, 2, 4], the XOR of the whole array is 7 != 0, so the answer is 3.
If nums = [0, 0], every subsequence has XOR 0, so the answer is 0.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Math / Bit Manipulation?

This problem maps to Math / Bit Manipulation through a short path in the full flowchart.

XOR properties reduce the problem to checking total XOR and zero count; the answer is always n, n-1, or 0.

Open in Flowchart

Intuition

The first natural thought is: since we want the longest subsequence, why not just take the entire array? Let's check its XOR:

If the XOR of all elements is non-zero, we are done — the whole array is the answer, and nothing longer exists. The answer is n.

Now, what if the XOR of the entire array is zero? Then we need to drop at least one element. Here is the key observation:

XOR has a useful property: if the total XOR is 0, and we remove an element x, the XOR of the remaining elements becomes 0 ^ x = x.
So if we remove a non-zero element x, the remaining n - 1 elements have XOR equal to x, which is non-zero. That gives us a valid subsequence of length n - 1.
Removing a zero element wouldn't help — the XOR would stay 0. That's why we must pick a non-zero element to remove.

This means as long as the array contains at least one non-zero element, we can always achieve length n - 1 when the total XOR is zero. And we cannot do better than n - 1, because the full array's XOR is zero.

The only remaining case is when every element is zero. Then any subsequence we pick will XOR to 0, so no valid subsequence exists, and the answer is 0.

Putting it together, the problem reduces to checking just two quantities:

The XOR of all elements — to see if we can take everything.
The count of zeros — to detect the all-zero case.

This turns what looks like a search over 2^n subsequences into a simple O(n) scan, which is why this problem is essentially a brain teaser rather than a dynamic programming or search problem.

Solution Approach

The implementation follows directly from the case analysis. We need only one pass through the array to gather two pieces of information:

xor — the bitwise XOR of all elements.
cnt0 — the number of zero elements.

Step-by-step walkthrough

Step 1: Initialize the accumulators.

n = len(nums)
xor = cnt0 = 0

Here n is the array length, xor will accumulate the XOR of all elements, and cnt0 counts how many zeros appear.

Step 2: Scan the array once.

for x in nums:
    xor ^= x
    cnt0 += int(x == 0)

For each element x, we fold it into the running XOR with xor ^= x, and increment cnt0 whenever x == 0.

Step 3: Decide the answer based on the three cases.

if xor:
    return n

If the total XOR is non-zero, the entire array is already a valid subsequence — and no subsequence can be longer than the array itself — so we return n.

if cnt0 == n:
    return 0

If every element is zero, every possible subsequence has XOR 0, so no valid subsequence exists and we return 0.

return n - 1

Otherwise, the total XOR is zero but at least one element is non-zero. Removing one non-zero element x leaves a subsequence whose XOR is 0 ^ x = x ≠ 0, so the answer is n - 1.

Why this is correct and optimal

The three cases are exhaustive: either the total XOR is non-zero, or it is zero with all elements zero, or it is zero with some non-zero element present.
In the last case, n - 1 is optimal because length n is impossible (the full array's XOR is zero), and length n - 1 is achievable as shown.

Complexity Analysis

Time complexity: O(n) — a single traversal of the array, where n is the length of nums.
Space complexity: O(1) — only two integer variables are maintained, regardless of input size.

Example Walkthrough

Let's trace the solution with nums = [3, 5, 6, 0].

Step 1: Initialize the accumulators.

n = 4
xor = 0
cnt0 = 0

Step 2: Scan the array once, updating xor and cnt0.

Element `x`	`xor ^= x` (running XOR)	Is `x == 0`?	`cnt0`
`3`	`0 ^ 3 = 3`	No	`0`
`5`	`3 ^ 5 = 6`	No	`0`
`6`	`6 ^ 6 = 0`	No	`0`
`0`	`0 ^ 0 = 0`	Yes	`1`

After the scan: xor = 0, cnt0 = 1.

Step 3: Apply the case analysis.

Is xor non-zero? No (xor = 0), so we cannot take the entire array — its XOR is 3 ^ 5 ^ 6 ^ 0 = 0.
Are all elements zero? No (cnt0 = 1, but n = 4), so a valid subsequence must exist.
Therefore we return n - 1 = 3.

Verifying the answer: Removing one non-zero element, say 6, leaves the subsequence [3, 5, 0] with XOR 3 ^ 5 ^ 0 = 6 ≠ 0. This subsequence has length 3, and length 4 is impossible since the full array XORs to zero — so 3 is indeed optimal.

Contrast with the other two cases:

If nums = [3, 5, 6, 1], the scan gives xor = 3 ^ 5 ^ 6 ^ 1 = 1 ≠ 0, so the first check fires immediately and we return n = 4 — the whole array works.
If nums = [0, 0, 0], the scan gives xor = 0 and cnt0 = 3 = n, so the second check fires and we return 0 — every subsequence is made entirely of zeros and must XOR to zero.

One linear pass and two simple checks cover all three possible outcomes: n, n - 1, or 0.

Solution Implementation

1class Solution:
2    def longestSubsequence(self, nums: List[int]) -> int:
3        n = len(nums)
4        total_xor = 0   # XOR of all elements in nums
5        zero_count = 0  # number of zeros in nums
6
7        # Compute the XOR of the whole array and count zeros in one pass
8        for num in nums:
9            total_xor ^= num
10            zero_count += int(num == 0)
11
12        # Case 1: XOR of all elements is non-zero,
13        # so the entire array is a valid subsequence
14        if total_xor:
15            return n
16
17        # Case 2: every element is zero,
18        # so no subsequence can have a non-zero XOR
19        if zero_count == n:
20            return 0
21
22        # Case 3: total XOR is zero but at least one element is non-zero.
23        # Removing one non-zero element makes the remaining XOR non-zero,
24        # so the answer is n - 1
25        return n - 1
26

1class Solution {
2    public int longestSubsequence(int[] nums) {
3        int totalXor = 0;      // XOR of all elements in the array
4        int zeroCount = 0;     // Number of zero elements in the array
5        int n = nums.length;   // Length of the array
6
7        // Traverse the array to compute the total XOR and count zeros
8        for (int num : nums) {
9            totalXor ^= num;
10            if (num == 0) {
11                zeroCount++;
12            }
13        }
14
15        // Case 1: If the XOR of all elements is non-zero,
16        // the entire array forms a valid subsequence.
17        if (totalXor != 0) {
18            return n;
19        }
20
21        // Case 2: The total XOR is zero.
22        // If every element is zero, no non-empty subsequence can have a non-zero XOR,
23        // so the answer is 0.
24        // Otherwise, removing one non-zero element makes the XOR of the remaining
25        // n - 1 elements non-zero, giving a valid subsequence of length n - 1.
26        return zeroCount == n ? 0 : n - 1;
27    }
28}
29

1class Solution {
2public:
3    int longestSubsequence(vector<int>& nums) {
4        // totalXor: XOR of all elements in the array
5        // zeroCount: number of elements equal to 0
6        int totalXor = 0;
7        int zeroCount = 0;
8        int n = nums.size();
9
10        // Compute the XOR of all elements and count zeros in one pass
11        for (int num : nums) {
12            totalXor ^= num;
13            zeroCount += (num == 0) ? 1 : 0;
14        }
15
16        // Case 1: If the XOR of all elements is non-zero,
17        // the entire array is a valid subsequence.
18        if (totalXor != 0) {
19            return n;
20        }
21
22        // Case 2: The XOR of all elements is zero.
23        // - If every element is 0, no non-empty subsequence can have a non-zero XOR,
24        //   so the answer is 0.
25        // - Otherwise, removing one non-zero element makes the XOR of the
26        //   remaining n - 1 elements non-zero.
27        return (zeroCount == n) ? 0 : n - 1;
28    }
29};
30

1/**
2 * Finds the length of the longest subsequence whose bitwise XOR is non-zero.
3 *
4 * Key observations:
5 * 1. If the XOR of all elements is non-zero, the entire array works,
6 *    so the answer is the array length.
7 * 2. If the XOR of all elements is zero and every element is zero,
8 *    no subsequence can have a non-zero XOR, so the answer is 0.
9 * 3. Otherwise (total XOR is zero but at least one element is non-zero),
10 *    removing one non-zero element makes the remaining XOR non-zero,
11 *    so the answer is the array length minus one.
12 *
13 * @param nums - The input array of numbers
14 * @returns The length of the longest valid subsequence
15 */
16function longestSubsequence(nums: number[]): number {
17    // XOR of all elements in the array
18    let totalXor: number = 0;
19    // Count of elements equal to zero
20    let zeroCount: number = 0;
21
22    // Accumulate the XOR and count the zeros in a single pass
23    for (const num of nums) {
24        totalXor ^= num;
25        zeroCount += num === 0 ? 1 : 0;
26    }
27
28    const n: number = nums.length;
29
30    // Case 1: total XOR is non-zero, take the whole array
31    if (totalXor !== 0) {
32        return n;
33    }
34
35    // Case 2: all elements are zero, no valid subsequence exists
36    if (zeroCount === n) {
37        return 0;
38    }
39
40    // Case 3: drop one non-zero element to make the XOR non-zero
41    return n - 1;
42}
43

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array nums. The code iterates through the array exactly once, and within each iteration, it performs only constant-time operations: the XOR accumulation xor ^= x and the zero-count update cnt0 += int(x == 0). The checks after the loop (if xor, if cnt0 == n) are also O(1), so the total running time is linear in the input size.
Space Complexity: O(1). Only a fixed number of integer variables (n, xor, cnt0, and the loop variable x) are used, regardless of the input size. No additional data structures that grow with n are allocated, so the extra space remains constant.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Returning `n - 1` without checking the all-zeros case

The most frequent mistake is collapsing the logic into just two branches:

# WRONG
if total_xor:
    return n
return n - 1

This looks plausible — "if the full XOR is zero, just drop one element" — but it silently breaks when every element is zero. For nums = [0, 0], the total XOR is 0, and this code returns 1. However, the remaining subsequence [0] still has XOR 0, so no valid subsequence exists and the correct answer is 0.

Why it happens: Removing an element x changes the XOR from 0 to 0 ^ x = x. This only produces a non-zero result when x itself is non-zero. If all elements are zero, removing elements never helps — every subsequence remains XOR 0.

Fix: Add the explicit all-zeros check before falling through to n - 1:

if total_xor:
    return n
if zero_count == n:   # all elements are zero -> no valid subsequence
    return 0
return n - 1          # safe: at least one non-zero element can be removed

Pitfall 2: Removing an arbitrary element instead of a non-zero one

A related reasoning error is assuming that when the total XOR is zero, removing any single element yields a non-zero XOR. Removing a 0 from the array leaves the XOR unchanged (0 ^ 0 = 0). The argument for n - 1 only works because we remove a non-zero element — which is guaranteed to exist precisely when zero_count < n. Code that tries to "construct" the subsequence by dropping nums[0] (which may be 0) and then verifying can produce incorrect or needlessly complicated logic. The clean fix is the case analysis above: no construction is needed, only the existence of one non-zero element.

Pitfall 3: Overcomplicating with DP or linear-basis techniques

Seeing "longest subsequence + XOR" tempts many into a subset-XOR dynamic programming table (O(n * max_xor)) or a Gaussian-elimination linear basis. Both are overkill here and can TLE or MLE on large inputs. The key observation that makes O(n) / O(1) possible:

If the full XOR ≠ 0 → answer is n (you can never do better than the whole array).
If the full XOR = 0 → length n is impossible, so n - 1 is the ceiling, and it's achievable iff a non-zero element exists.

The answer is always one of n, n - 1, or 0 — no search over subsequences is required.

Pitfall 4: Forgetting that the subsequence must be non-empty

Some implementations treat the empty subsequence (XOR = 0 by convention) as a candidate or, conversely, return 0 thinking "empty is the fallback" when in fact 0 should only be returned in the all-zeros case. Keep the contract clear: the answer is 0 only when every element of nums is zero.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

How does quick sort divide the problem into subproblems?

Divide the array into two equal halves by index

Divide the array into two based on whether an element is smaller than an arbitrary value

Divide the array into a stray element and the rest of the array

Quick sort does not use divide and conquer

I don't know