1308. The Largest OR and the Largest AND of Any Stretch
Among all n(n+1)/2 contiguous stretches, find the largest bitwise OR of a
stretch and the largest bitwise AND of a stretch. Print the two, OR first.
12 10 6 14 -> 14 14
0 5 9 -> 13 9
1 2 4 8 16 -> 31 16
## What most people try first
Every stretch, with running accumulators. That is O(n^2), which at
n = 200000 is 2 * 10^10 stretches. It is correct and it is the oracle's
brute force.
What makes this problem worth having is that no search is needed at all, in either direction, and the two answers come from opposite ends of the same argument.
## The largest OR is the OR of everything
OR never clears a bit, so extending a stretch can only add bits and therefore
can only increase the value: OR(l..r) <= OR(l..r+1). So for any stretch, the
WHOLE array is at least as large, and the maximum is
OR(a[0] .. a[n-1])
computed in one pass. There is no stretch that does better, because every stretch's OR is a submask of the whole array's OR, and a submask is never numerically larger.
## The largest AND is the largest single element
AND never sets a bit, so extending a stretch can only remove bits and therefore
can only decrease the value: AND(l..r) >= AND(l..r+1). So the best stretch is
as SHORT as possible, which means length one, and the maximum is
max(a[0], ..., a[n-1])
The bound is reached, by the single-element stretch holding the maximum, so it is exact rather than an upper limit.
This is the same observation #714 uses, and that problem asks a different question with it: the LENGTH of the longest stretch achieving this maximum AND. Here the value itself is asked for, and the OR half has no counterpart there.
## Why the two answers are often equal, and when they are not
On 12 10 6 14 both are 14, because the maximum element already contains every
bit any value contributes. They differ as soon as two values have bits the other
lacks: on 0 5 9 the OR is 13 and the largest element is 9, and on
1 2 4 8 16 the OR is 31 while the largest element is 16.
The general relation is that the largest AND is at most the largest OR, since the maximum element is a submask of the total OR. Equality holds exactly when some single element already ORs to the whole array's OR.
## Cost
Two accumulators in one pass: O(n) time and O(1) space, against O(n^2).
## Width
Values are at most 1073741823, which is 2^30 - 1, so every AND and OR stays
below 2^30 and fits in a signed 32-bit integer, whose limit is 2147483647,
with one bit to spare. JavaScript's & and | are safe on plain Numbers.
Nothing accumulates in a way that can overflow: an OR is bounded by the OR of everything and an AND by the largest input, so unlike a sum neither can exceed the input range however many values there are.
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ a[i] ≤ 1073741823`
Input
The first line contains the integer n.
The second line contains n integers.
Output
Print two integers on one line separated by a single space: the largest bitwise OR of any contiguous stretch, then the largest bitwise AND of any contiguous stretch.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.