Longest Subsequence with a Nonzero XOR

### Problem Given an integer array `nums`, return the greatest length of a subsequence whose bitwise XOR is nonzero. If no such subsequence exists, return `0`. A subsequence is obtained by deleting zero or more positions while preserving the order of the remaining positions. It need not be contiguous. Only its length is required as output. ```cpp class Solution { public: int longestSubsequence(vector<int>& nums); }; ``` ### Examples **Example 1:** ```text Input: nums = [5,5,0] Output: 2 Explanation: The whole array has XOR zero. The subsequence [5,0] has XOR 5 and length two, so the maximum is two. ``` **Example 2:** ```text Input: nums = [0,0,0] Output: 0 Explanation: Every subsequence has XOR zero, so none meets the requirement. ``` ### Constraints - `1 <= nums.length <= 100000`. - `0 <= nums[i] <= 1000000000`. ### Clarifying Questions - Must the selected positions be consecutive? No. - Do duplicate values use separate positions? Yes. - Can zero-valued entries occur in a valid subsequence? Yes; the XOR of the entire selection must be nonzero. - Must the chosen subsequence itself be returned? No, return its length. ### What a Strong Answer Covers - The subsequence and nonzero-XOR requirements for all allowed values. - A reason the reported length is attainable and no longer valid choice exists. - Zero entries, repeated values, and a single-element input. - Correct failure behavior and resource bounds at the maximum input size. ### Follow-up Questions - How could requesting every optimal subsequence change the amount of output? - What additional output would be required to return a witnessing subsequence? ```hint Compare the longest possible selection first Examine the XOR of the whole array. If it is zero, use XOR cancellation to reason about omitting one nonzero entry. Handle the all-zero case separately. ```