Is Longest Subsequence With Non-Zero Bitwise XOR easy or hard?

The problem is typically rated Medium because the trick is recognizing the XOR identity rather than brute forcing subsequences. Once the XOR property is understood, the implementation becomes straightforward with O(n) time and constant space.

Longest Subsequence With Non-Zero Bitwise XOR Python/Java solution

The implementation is very short in Python, Java, C++, Go, or TypeScript. Compute the XOR of all elements in one loop, check if the result is zero, and verify whether all numbers are zero. Based on those checks, return n, n-1, or 0 accordingly.

How to solve Longest Subsequence With Non-Zero Bitwise XOR in O(n)?

First compute the XOR of all elements in the array. If the result is non-zero, return the array length n. If the total XOR equals zero, remove one non-zero element so the remaining XOR becomes that element's value, producing a subsequence of length n-1. If all elements are zero, no valid subsequence exists and the answer is 0.

What is the best approach for Longest Subsequence With Non-Zero Bitwise XOR?

The optimal approach uses a simple XOR observation. Compute the XOR of the entire array. If it is non-zero, the longest valid subsequence is the full array. If it equals zero, removing any non-zero element makes the remaining XOR non-zero, giving a subsequence of length n-1. This runs in O(n) time and O(1) space.

Is Longest Subsequence With Non-Zero Bitwise XOR asked at Google/Amazon/Meta?

Problems involving XOR properties and subsequences appear frequently in interviews at companies like Google, Amazon, and Meta. While this exact question may vary, the XOR reasoning pattern and bit manipulation insights are commonly tested in medium-level coding interviews.

What data structure is used in Longest Subsequence With Non-Zero Bitwise XOR?

The optimal solution does not require advanced data structures. It uses simple array traversal and bitwise XOR operations. Understanding bit manipulation identities is more important than using extra storage or complex structures.

What is the time complexity of Longest Subsequence With Non-Zero Bitwise XOR?

The optimal solution runs in O(n) time because you only scan the array once to compute the total XOR and check for non-zero elements. The space complexity is O(1) since only a few variables are used regardless of input size.

Description Hints 3 Solution Video 7:39

3702. Longest Subsequence With Non-Zero Bitwise XOR

Medium55.1% acceptance

You are given an integer array nums.

Return the length of the longest subsequence in nums whose bitwise XOR is non-zero. If no such subsequence exists, return 0.

Example 1:

Input: nums = [1,2,3]

Output: 2

Explanation:

One longest subsequence is [2, 3]. The bitwise XOR is computed as 2 XOR 3 = 1, which is non-zero.

Example 2:

Input: nums = [2,3,4]

Output: 3

Explanation:

The longest subsequence is [2, 3, 4]. The bitwise XOR is computed as 2 XOR 3 XOR 4 = 5, which is non-zero.

Constraints:

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁹

Topics

Array Bit Manipulation

Hints open one at a time

Hint 1

What happens if you take the entire array?

Hint 2

If the XOR of the entire array is 0, can removing one element help?

Hint 3

What if all elements are 0?

7:39

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def longestSubsequence(self, nums: List[int]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[1,2,3]

Input

[2,3,4]

Your code is saved on this device.Solution