1312. The Longest Stretch Whose AND Stays at k or Above

Find the longest contiguous stretch whose bitwise AND is at least k, and print its length. Print 0 if no stretch qualifies.

n=4 k=8, 12 10 6 14 -> 2 12 10 ANDs to 8 n=4 k=15, 15 15 15 7 -> 3 n=2 k=1, 0 0 -> 0

## What most people try first

Every stretch, which is O(n^2). Or a two-pointer window with a running AND, which fails for the reason #1311 gives: AND is not invertible, so removing an element from an accumulated AND is impossible. A bit that is 0 in the accumulator might be 0 because of the element being removed, or because of three others, and the accumulator does not say which.

A third instinct is that the answer is related to the maximum element, because #1308 says the LARGEST subarray AND is the largest element. That is about the largest VALUE, not the longest stretch at a threshold, and the two have nothing to do with each other: on 15 15 15 7 the largest AND is 15 and the longest stretch with AND at least 15 has length 3, while on 6 14 30 the largest AND is 30 and the longest stretch with AND at least 6 has length 3.

## Counts per bit again, with the AND recovered differently

counts[b] = how many elements of the window have bit b set AND of window = the bits b with counts[b] == window length

The second line is the only difference from #1311: a bit survives an AND exactly when EVERY element has it, which is what "count equals length" says. Adding and removing elements updates the counts exactly, because counting is invertible even though AND is not.

## Why a two-pointer sweep is valid, and which way it goes

#1307 establishes that AND is non-increasing as a window grows. So for a fixed left end, the right ends whose stretch has AND at least k form a PREFIX: once the AND has fallen below k, extending further keeps it below.

That is the opposite shape from #1311, where the valid right ends formed a suffix, and it changes the sweep. Here, after extending hi, the window may have become INVALID, so shrink from lo until it is valid again, and then record the length. In #1311 the window may have become VALID, so shrink while it STAYS valid, recording as you go.

Getting that backwards is the characteristic bug in this pair of problems, and it does not always show: on inputs where every window is valid both loops give the same answer. The declared test 4 8 / 12 10 6 14 has answer 2 and the #1311-shaped loop gives 1.

Both pointers still advance monotonically, because as lo moves right the window's AND can only rise, so a window that was invalid cannot become invalid again at a smaller size for the same hi. Hence O(n) pointer movements with O(30) work each.

## The empty-window case

When no single element is at least k, every window is invalid and lo passes hi, leaving an empty window. The answer is then 0, which is why the contract asks for 0 rather than -1 here while #1311 asks for -1: a length of 0 is a meaningful answer for "longest" and not for "shortest".

## 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 relevant ones and every AND stays below 2^30, fitting in a signed 32-bit integer whose limit is 2147483647. The counts are bounded by n = 200000, and the answer is a length at most 200000.

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

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