All Tracks Algorithms Greedy Algorithms Basics of Greedy Algorithms Problem

Subxor
/

Algorithms, Greedy Algorithms

Problem
Editorial
Analytics

You are provided an array \(A\) of \(n\) integers. You are required to partition the array into the minimum number of subarrays such that the \(XOR\) of any non-empty subset of the subarrays is not equal to zero. If no such partition exists, then print \(-1\). Otherwise, print 1.

Note:

  • A subarray is a non-empty contiguous subsequence of an array.
  • The \(XOR\) of a set of subarrays is defined as the sum of determined \(XORs\) of the numbers in all the subarrays when accumulated.

Input format

The first line consists of an integer \(n\) that is followed by \(n\) space-separated integers.

Output format

Print the answer in a single line.

Constraints

\(1\leq n\leq 5*10^5\)

\(0\leq A[i]\leq 10^9\)

SAMPLE INPUT
2
2 2
SAMPLE OUTPUT
-1
Explanation

The possible partitions of the array are: [2],[2] but the xor of both the subarrays is 0 and [2,2] where the xor of this subarray itself is 0. Hence the answer is -1.

Time Limit: 5.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?