Longest Subsequence With Non-Zero Bitwise XOR - Solution & Explanation

Problem Overview: Given an integer array, select the longest subsequence whose bitwise XOR is not equal to 0. The challenge is recognizing how XOR behaves when elements are included or removed from a sequence.

Approach 1: Brute Force Subsequence Enumeration (O(2^n) time, O(1) space)

Generate every possible subsequence and compute its XOR. Track the maximum length among those whose XOR is non-zero. This can be done with recursion or bitmask enumeration where each mask represents a subsequence. For every mask, iterate through the array and XOR the selected elements. The approach quickly becomes infeasible because the number of subsequences grows as 2^n. It mainly serves as a conceptual baseline for understanding the problem.

Approach 2: XOR Observation / Brain Teaser (O(n) time, O(1) space)

The key insight comes from XOR properties. Compute the XOR of the entire array. If the result is already non-zero, the optimal subsequence is simply the entire array because adding more elements cannot increase the length. If the total XOR equals 0, removing exactly one element changes the XOR to that element's value because total_xor ^ nums[i] = nums[i]. As long as the removed element is non-zero, the remaining subsequence will have a non-zero XOR and length n - 1.

The only case where a non-zero XOR subsequence cannot exist is when every element in the array is 0. Any subsequence XOR will still be 0. In that scenario, the answer is 0. Otherwise, if the total XOR is zero but at least one number is non-zero, remove one non-zero element and return n - 1.

This solution relies purely on XOR algebra rather than complex data structures. You only need one pass to compute the total XOR and check whether all elements are zero. The algorithm works efficiently even for very large arrays because it performs constant-time operations per element.

Understanding XOR identities like a ^ a = 0 and x ^ 0 = x is essential for problems involving bit manipulation. Many interview problems involving subsequences or parity rely on similar observations. Since the input is simply processed sequentially, the logic fits naturally with common array traversal patterns.

Recommended for interviews: Interviewers expect the XOR observation approach. Starting with the brute force explanation demonstrates understanding of subsequences, but recognizing the XOR identity that reduces the problem to a simple check shows strong problem-solving intuition. The optimal solution runs in O(n) time with O(1) extra space.