675. Pairs Whose Product Stays Under a Limit

Given n positive integers and a limit, count the pairs of POSITIONS i < j whose values MULTIPLY to strictly less than the limit.

1 2 3 4, limit 7 -> 4 (1,2) (1,3) (1,4) (2,3) 1 1 1, limit 2 -> 3 5 6 7, limit 10 -> 0

## The block count, with a product instead of a sum

Sort, then sweep from both ends. When a[i] * a[j] is under the limit, every partner between i and j is at most a[j], and the values are POSITIVE, so every one of those products is also under the limit.

if a[i] * a[j] < limit: count += j - i; i += 1 else: j -= 1

That is j - i pairs from one comparison, exactly the shape of problem 608 with the sum replaced by a product.

## Why positivity is required, not decorative

The step "a smaller partner gives a smaller product" is only true for positive values. With a negative value in play, multiplying by something smaller can make the product LARGER, and the block count collapses.

The constraint says positive precisely so the same sweep transfers from sums to products. When a problem changes the operation, the first question is whether the monotonicity the sweep relies on still holds.

## Overflow before comparison

Two values near 10^9 multiply to 10^18. That fits comfortably in a signed 64 bit integer, whose limit is about 9.2 * 10^18, so C, C++ and Java can compare the product directly. It does NOT fit in 32 bits.

JavaScript is the exception: 10^18 is past the exact integer range of a double, so the product must be computed with big integers or the comparison rewritten as a division.

## The strictness

The limit is exclusive: a product EQUAL to the limit does not count. 2 2 with limit 4 answers 0 and with limit 5 answers 1, and those two inputs pin it.

## Overflow in the count

C(200000, 2) is about 2 * 10^10, so the count needs 64 bits too.

## Cost

Time O(n log n) for the sort. Space O(1) beyond the input.

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