733. The Longest Stretch That Cancels Out
Find the longest contiguous stretch whose bitwise XOR is 0, and print its length. Print 0 if
no such stretch exists.
4 2 2 6 4 -> 3 the stretch 2 6 4, since 2 ^ 6 ^ 4 is 0
1 2 3 -> 3
0 0 0 -> 3
5 -> 0
## The XOR is zero exactly when two prefixes agree
The stretch from i+1 to j has XOR P[j] ^ P[i], and that is 0 exactly when
P[i] == P[j]
So the question becomes: over all pairs of EQUAL prefix values, which pair is furthest apart.
## Keep the FIRST index, not the last
For each prefix value, remember the earliest position at which it appeared. When that value
comes round again at position j, the stretch is j minus that earliest index, which is the
longest one ending at j.
Overwriting with the latest index instead gives the SHORTEST such stretch and quietly returns a
smaller answer. Nothing crashes, and on many inputs the two agree, which is what makes it hard
to spot. It takes a prefix value that recurs at least three times to separate them: 0 0 0
answers 3 with the first index and 1 with the last, and 1 2 3 0 answers 4 against 3.
This is the one difference from problem 732, which COUNTS and therefore needs a tally of how many times each prefix appeared rather than where it first did. Same prefix array, different bookkeeping, and choosing between them is the skill.
## The empty prefix again
Record that prefix 0 first appears at index 0, before the sweep. That is what lets a stretch
starting at position 1 be found, and 1 2 3 answering 3 depends on it entirely, because
1 ^ 2 ^ 3 is 0 and there is no other way to reach it.
## Why a zero in the array always gives at least 1
A single 0 is a stretch whose XOR is 0. So any array containing a zero answers at least 1, and
an array of all zeros answers n.
## Relationship with problem 299
299 finds the longest stretch with equal counts of 0 and 1, by mapping 0 to -1 and looking
for a repeated prefix SUM. This looks for a repeated prefix XOR. Two different encodings, one
identical idea: turn "this stretch is balanced" into "these two prefixes are equal".
## Overflow
Nothing here overflows. A prefix XOR never sets a bit that none of its inputs had, so it stays
inside the WIDTH of those inputs, unlike a prefix sum which grows without bound. That is a
statement about bit width and not about magnitude, since XOR can exceed both its operands:
1 ^ 2 = 3.
The values reach 10^9, and 10^9 < 2^30 = 1073741824, so every prefix XOR stays below
2^30. The sign bit of a 32 bit integer is therefore never set and the usual advice to reach
for an unsigned type in C and C++ has nothing to bite on here. It would start to matter only if
the value bound were raised past 2^31.
## Cost
Time O(n). Space O(n).
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ each value ≤ 10^9`
Input
The first line contains an integer n.
The second line contains n integers.
Output
Print one integer, the length of the longest stretch whose XOR is 0.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.