1310. How Many Stretches Have an OR of Exactly k
Count the contiguous stretches whose bitwise OR equals exactly k.
n=4 k=14, 12 10 6 14 -> 7
n=4 k=15, 15 15 15 7 -> 9
n=5 k=31, 1 2 4 8 16 -> 1
## What most people try first
Every stretch, which is O(n^2). The improvement is #1309's, with AND replaced
by OR, and the mirroring is exact enough that it is worth stating precisely
rather than waving at.
## The mirror of #1309
Fix a right endpoint r and list the ORs of all stretches ending there, in
order of increasing length:
a[r], a[r-1] | a[r], a[r-2] | a[r-1] | a[r], ...
Each term is the previous term ORed with one more value, so each term is a SUPERMASK of the previous one. Moving along the list, a value either stays the same or gains at least one bit, and it can never lose one.
A value below 2^30 has at most 30 bits to gain. So there are at most 30
points at which the value changes, hence at most 31 distinct values in the list,
whatever n is. The bound is on the width, exactly as in #1309.
So the algorithm is #1309's with two characters changed:
next = { a[r] : 1 }
for (value, count) in current:
next[value | a[r]] += count
current = next
answer += current.get(k, 0)
## The one place the mirroring is not symmetric
#1309's list is non-increasing and this one is non-decreasing, which matters for a threshold question but not for equality: both are monotone, and in both cases the distinct values are few. So for THIS question the two problems really are mirror images.
Where they stop mirroring is in the extremes. The largest OR of any stretch is the OR of everything and the smallest is the smallest single element, while the largest AND is the largest single element and the smallest is the AND of everything, which is #1308's subject. A solution that mirrors the ALGORITHM correctly but carries over a claim about the extremes will be wrong.
## Why the counts are needed
On 15 15 15 7 the answer is 9 while only two distinct OR values occur, 15 and
7. Dropping the multiplicities would answer 2. The distinct-value question is
asked for AND in #1315.
## Width
Values and k are at most 1073741823, which is 2^30 - 1, so every OR 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 count reaches n(n+1)/2 = 20000100000 at n = 200000 when every stretch
qualifies, about nine times past 2147483647, so the accumulator must be
64 bit. In JavaScript it is below 2^53 = 9007199254740992 and a Number
counter stays exact. As in #1309, no declared test reaches that magnitude
because a literal input doing so needs 200000 values, so the bound is argued
rather than tagged.
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ k ≤ 1073741823` - `0 ≤ a[i] ≤ 1073741823`
Input
The first line contains two integers n and k, separated by a space.
The second line contains n integers.
Output
Print one integer on its own line: how many contiguous stretches have a bitwise OR equal to k. Print 0 if none do.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.