689. Stretches Whose Product Stays Below a Limit

Given n positive integers and a limit, count the CONTIGUOUS stretches whose product is strictly less than the limit.

10 5 2 6, limit 100 -> 8 1 1 1, limit 2 -> 6 1 2 3, limit 1 -> 0

## Count the windows ending at each position

Grow the window on the right, multiplying the running product. While the product is at or above the limit, divide out the leftmost value and advance the left edge.

Then every stretch ENDING at hi and starting anywhere from lo to hi is valid, and there are hi - lo + 1 of them.

p *= a[hi] while p >= limit and lo <= hi: p /= a[lo]; lo += 1 count += hi - lo + 1

Counting the windows that END at each position is the standard way to turn a "longest" sweep into a "how many" sweep, and it appears again in 690, 697 and 698.

## Why dividing out is exact

All values are positive INTEGERS and the running product is the product of exactly the values in the window, so dividing by a[lo] removes it exactly with no rounding.

With a zero in the array the product would collapse to zero and never recover; with a fraction the division would not be exact. The constraint that values are at least 1 is what keeps this sound.

## The lo <= hi guard

A single value at or above the limit forces the window empty. The guard stops lo running past hi and then dividing by something outside the window.

10 with limit 5 answers 0, and that input is the test.

## Why limit <= 1 answers 0 immediately

The smallest possible product is 1, from a single value of 1, so nothing is strictly below 1. Handling it up front avoids the loop having to reason about an empty window at every step.

## Overflow

The running product is kept below the limit by the shrink step, so it never exceeds limit * max_value before being divided down. With a limit up to 10^9 and values up to 10^9 that is 10^18, which needs 64 bits.

## Cost

Time O(n). Space O(1).

Constraints - `1 ≤ n ≤ 200000` - `1 ≤ each value ≤ 1000` - `0 ≤ limit ≤ 10^9`