1311. The Shortest Stretch Whose OR Reaches k

Find the shortest contiguous stretch whose bitwise OR is at least k, and print its length. Print -1 if no stretch reaches k.

n=4 k=14, 12 10 6 14 -> 1 the single element 14 n=5 k=31, 1 2 4 8 16 -> 5 everything is needed n=1 k=8, 7 -> -1

## What most people try first

A two-pointer window, which is the right idea, and then getting stuck on how to REMOVE an element from the window. A running sum can be decremented; a running OR cannot, because OR is not invertible. Once a bit is in the accumulator there is no way to tell whether one element or five contributed it, so or_value ^ a[lo] is wrong and or_value & ~a[lo] is worse: it clears bits that other elements in the window still provide.

This is the single most useful thing to know about sliding a window over a non-invertible operation.

## Keep a count per bit position instead of a value

counts[b] = how many elements of the window have bit b set

Adding an element increments the counts for its bits; removing one decrements them. Both are exact, because a count IS invertible even though an OR is not. Then the window's OR is recovered whenever it is needed:

OR of window = the bits b with counts[b] > 0

which is 30 tests. The AND would be the bits with counts[b] == window length, which is #1312's version of the same idea.

## Why a two-pointer sweep is valid

#1307 establishes that OR is non-decreasing as a window grows. So for a fixed left end, the right ends whose stretch reaches k form a SUFFIX: once the OR is large enough, extending further keeps it large enough.

Hence for each left end there is a minimal valid right end, and as the left end moves RIGHT the window loses elements, the OR can only fall, and that minimal right end can only move right too. Both pointers advance monotonically, so the total work is O(n) pointer movements with O(30) work each.

Concretely: extend hi by one, then while the window still reaches k, record its length and shrink from lo. Shrinking while still valid is what finds the SHORTEST window ending at each hi.

## Why the comparison is numeric and not a mask test

The requirement is "OR at least k" as NUMBERS, not "OR contains k's bits". Those differ: OR = 16 is numerically at least k = 15 while containing none of k's bits. The declared test 5 31 / 1 2 4 8 16 answers 5 because reaching 31 numerically here does require every element, and 4 16 / 15 15 15 7 answers -1 because no OR of those values reaches 16 at all.

## Cost

O(30 n) time, about 6 * 10^6 operations at n = 200000, and O(30) space.

## Width

Values and k are at most 1073741823, which is 2^30 - 1, so positions 0 to 29 are the only ones that matter, every OR stays below 2^30, and the bit arithmetic fits in a signed 32-bit integer whose limit is 2147483647. The counts are bounded by n = 200000 and also fit. The answer is a length, at most 200000.

Nothing here needs 64 bits and JavaScript is safe with plain Numbers, since every operand already fits in signed 32 bits.

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ k ≤ 1073741823` - `0 ≤ a[i] ≤ 1073741823`