1309. How Many Stretches Have an AND of Exactly k
Count the contiguous stretches whose bitwise AND equals exactly k.
n=4 k=8, 12 10 6 14 -> 1
n=4 k=15, 15 15 15 7 -> 6
n=6 k=2, 2 2 6 2 3 2 -> 19
## What most people try first
Every stretch with a running AND, which is O(n^2) and 2 * 10^10 stretches at
n = 200000.
The next instinct is a two-pointer window, because #1307's monotonicity says the
AND falls as the window grows. That works for a THRESHOLD, which is #1312's
problem, and it does not work for EQUALITY: the stretches whose AND equals k
do not form a contiguous range of lengths for a fixed left end, they form a
contiguous range for each left end, and counting those ranges still needs the
boundaries, which a single window does not give.
## The set of ANDs ending at one position is tiny
Fix a right endpoint r and consider the ANDs of all stretches ending there:
AND(r..r), AND(r-1..r), AND(r-2..r), ...
As the left end moves outward the AND only loses bits, so this list is
non-increasing, and each step either keeps the value or drops at least one bit.
A value below 2^30 has at most 30 bits, so at most 30 DROPS can happen. So
the list has at most 31 DISTINCT values however long the array is.
That is the whole insight. Keep those distinct values with multiplicities, as a map from value to how many left ends produce it, and extend it by one position:
next = { a[r] : 1 }
for (value, count) in current:
next[value & a[r]] += count
current = next
answer += current.get(k, 0)
Every stretch ending at r is accounted for exactly once, because the map is
built from every stretch ending at r - 1 extended by a[r], plus the
single-element stretch a[r] itself. Summing current[k] over all r counts
every qualifying stretch once, at its right endpoint.
## Cost
O(n log V) time, where log V is 30 here: at most 31 entries per position and
a constant amount of work each. O(log V) space. Against O(n^2).
Compare #1315, which keeps the same structure but as a SET without multiplicities, because it asks how many distinct AND values exist rather than how many stretches produce one. The structure transfers; what changes is what is stored in it.
## Why the multiplicities are needed here
Without counts the map would say WHICH values occur but not how many stretches
give each. On 15 15 15 7 the answer is 6, which is the number of stretches,
while the number of distinct AND values is only 2. Dropping the counts turns
this problem into #1315's.
## Width
Values and k 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 COUNT is the wide quantity. With n = 200000 identical values and k equal
to that value, every one of the n(n+1)/2 = 20000100000 stretches qualifies,
which is about 2 * 10^10 and roughly nine times past 2147483647. So the
accumulator must be 64 bit even though every value is 30 bits. In JavaScript the
total is well below 2^53 = 9007199254740992, so a plain Number counter stays
exact. No declared test reaches that magnitude, because a literal input doing so
needs 200000 numbers; the bound is argued rather than tagged on a test that
would not demonstrate it.
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 AND 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.