Skip to content

3702. Longest Subsequence With Non-Zero Bitwise XOR

Description

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 <= 105
  • 0 <= nums[i] <= 109

Solutions

Solution 1: Brain Teaser

If the bitwise XOR of all elements in the array is non-zero, then the entire array is the desired longest subsequence, with length equal to the array length.

If all elements in the array are zero, then there is no subsequence with non-zero bitwise XOR, so we return \(0\).

Otherwise, we can remove one non-zero element from the array to make the bitwise XOR of the remaining elements non-zero. The length of the longest subsequence is the array length minus \(1\).

The time complexity is \(O(n)\), where \(n\) is the length of array \(\textit{nums}\). The space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def longestSubsequence(self, nums: List[int]) -> int:
        n = len(nums)
        xor = cnt0 = 0
        for x in nums:
            xor ^= x
            cnt0 += int(x == 0)
        if xor:
            return n
        if cnt0 == n:
            return 0
        return n - 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int longestSubsequence(int[] nums) {
        int xor = 0, cnt0 = 0;
        int n = nums.length;
        for (int x : nums) {
            xor ^= x;
            cnt0 += x == 0 ? 1 : 0;
        }
        if (xor != 0) {
            return n;
        }
        return cnt0 == n ? 0 : n - 1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int longestSubsequence(vector<int>& nums) {
        int xor_ = 0, cnt0 = 0;
        int n = nums.size();
        for (int x : nums) {
            xor_ ^= x;
            cnt0 += x == 0 ? 1 : 0;
        }
        if (xor_ != 0) {
            return n;
        }
        return cnt0 == n ? 0 : n - 1;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func longestSubsequence(nums []int) int {
    var xor, cnt0 int
    for _, x := range nums {
        xor ^= x
        if x == 0 {
            cnt0++
        }
    }
    n := len(nums)
    if xor != 0 {
        return n
    }
    if cnt0 == n {
        return 0
    }
    return n - 1
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
function longestSubsequence(nums: number[]): number {
    let [xor, cnt0] = [0, 0];
    for (const x of nums) {
        xor ^= x;
        cnt0 += x === 0 ? 1 : 0;
    }
    const n = nums.length;
    if (xor) {
        return n;
    }
    if (cnt0 === n) {
        return 0;
    }
    return n - 1;
}

Comments