Zero XOR | Practice Problems

Zero XOR

★★★★★

1 votes

Binary search algorithm, Medium, Algorithms, Algorithms, Meet in the Middle, Binary Search, Arrays, Searching, Searching algorithm

Details

Submissions

Discussion

Editorial

Problem

A zero XOR subset is a non-empty subset that contains XOR of all the elements in it that is equal to $0$ . You are given an array of $N$ numbers.
You are required to determine the number of different zero XOR subsets of this array.

Input format

First line: A number $N$ denoting the length of the array
Second line: $N$ elements of the array

Output format
Print the single number denoting the count of zero XOR subsets of the given array.

Constraints
$1\le N\le 40\\ 1\le a[i]\le 10^{18}$

Sample Input

3
1 2 3

Sample Output

Time Limit: 5

Memory Limit: 256

Source Limit:

Explanation

For [1, 2, 3] ,there is only 1 subset (1, 2, 3) having Xor (1 ^ 2 ^3) = 0.
So, the answer is 1.

Contributers:

Mayank Garg