1315. How Many Different ANDs the Stretches Produce
Consider the bitwise AND of every contiguous stretch. Print how many DISTINCT values occur among them.
12 10 6 14 -> 7
15 15 15 7 -> 2
1 2 4 8 16 -> 6
2 2 6 2 3 2 -> 3
## What most people try first
Computing all n(n+1)/2 ANDs and putting them in a set, which is O(n^2) and
2 * 10^10 stretches at n = 200000.
The tempting shortcut is to bound the answer and hope it is small: the AND of
any stretch is a submask of some element, so the answer is at most the number of
distinct submasks of the elements. That bound is 2^30 and useless. The answer
really can be large, and it must be computed rather than bounded.
## The same structure as #1309, with a different payload
#1309 establishes the key fact. Fix a right endpoint r and list the ANDs of
the stretches ending there. Each is a submask of the previous, so the list only
loses bits, and a 30-bit value can lose a bit at most 30 times. So there are at
most 31 DISTINCT values among the stretches ending at any given position.
#1309 stores those values with multiplicities, because it counts stretches. Here multiplicities are irrelevant, so store a plain SET and union it into a global one:
seen = empty set
cur = empty set
for v in a:
cur = { v } union { w & v for w in cur }
seen = seen union cur
answer = size of seen
cur after processing position r is exactly the set of ANDs of stretches
ending at r, because every such stretch is either a[r] alone or a stretch
ending at r-1 extended by a[r]. Unioning all of them over all r gives
every stretch's AND exactly once as a VALUE, which is what is asked.
## Why the bound on the set size is the whole algorithm
cur has at most 31 elements at every step, so each step costs O(31) AND
operations plus set insertions. The global seen can grow large, but inserting
into it is O(1) expected, and its final size IS the answer.
So the cost is O(n log V) where log V is 30, about 6 * 10^6 operations at
n = 200000, against O(n^2).
## Where the answers come from on the samples
On 15 15 15 7 every stretch ANDs to either 15 or 7, so the answer is 2 while
#1309 with k = 15 answers 6. That pair of inputs is the clearest statement of
the difference between the two problems.
On 1 2 4 8 16 the five singletons give five distinct values and every
multi-element stretch gives 0, so the answer is 6.
On 2 2 6 2 3 2 the distinct values are 2, 6 and 3, so 3.
## Width
Values are at most 1073741823, which is 2^30 - 1, so every AND stays below
2^30 and the bit arithmetic fits in a signed 32-bit integer, limit
2147483647. JavaScript's & is safe on plain Numbers.
The ANSWER is a count of distinct values, bounded by the number of stretches and
also by 2^30, so it is at most about 10^9 and fits in a signed 32-bit
integer as well. That is a real difference from #1309, whose count of stretches
reaches 2 * 10^10 and needs 64 bits: counting VALUES is bounded by the value
space, and counting STRETCHES is bounded by n^2. Nothing here needs 64 bits.
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ a[i] ≤ 1073741823`
Input
The first line contains the integer n.
The second line contains n integers.
Output
Print one integer on its own line: how many distinct values occur as the bitwise AND of some contiguous stretch.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.