696. The Longest Stretch Sharing No Bits
Find the longest contiguous stretch in which no two values share a set bit. Print its length.
Two values share a bit when their bitwise AND is non zero, so the requirement is that EVERY pair inside the stretch has AND equal to zero.
1 3 8 48 10 -> 3 3 8 48 is 11, 1000, 110000
3 1 5 11 13 -> 1
1 2 4 8 -> 4
0 0 0 -> 3
## Checking every pair is not needed
If the values already inside the window are pairwise disjoint, their OR has exactly the bits that appear, each contributed by exactly one value. So a new value conflicts with SOMETHING in the window precisely when
a[hi] & (OR of the window) != 0
One AND replaces up to n pairwise checks. That step is the problem.
## Removal is XOR, not recomputation
Because each bit in the running OR came from exactly one value, dropping a[lo] removes
exactly its bits:
cur ^= a[lo]
XOR is correct here only BECAUSE the window is pairwise disjoint. In a window that allowed sharing, XOR would clear a bit still owned by someone else, and the OR would have to be rebuilt from scratch. The invariant is what makes the cheap removal legal, which is worth saying out loud rather than discovering by accident.
## The sweep
for hi in 0 .. n-1:
while cur & a[hi]:
cur ^= a[lo]; lo += 1
cur |= a[hi]
best = max(best, hi - lo + 1)
The shrink loop terminates: once lo reaches hi the window is empty, cur is 0, and
0 & a[hi] is 0.
## Zeros
A zero shares no bit with anything, so a run of zeros is entirely valid and 0 0 0 answers 3.
That is the case an implementation that special-cases "empty window" tends to get wrong.
## Boundaries
A single value always answers at least 1, including when that value is 7 and nothing can join it. Powers of two in a row answer the whole length.
## Cost
Time O(n), since lo only advances. Space O(1).
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 values pairwise share no bit.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.