Window product stays under a limit
Updated
Keep prod = product of a[L..R]. Expand: prod *= a[R]. While prod >= limit, prod /= a[L], L++. Valid windows have prod < limit.
What to focus on
Needs positive integers so divide undoes multiply. Count or length uses the valid [L,R] after the while.
Worked examples
limit 10
a = [1, 2, 3, 4], limit 10- [1,2,3] prod 6 < 10
- *4 → 24
- drop 1 → 24, drop 2 → 12, drop 3 → 4
Result: [4] prod 4 < 10
limit 7
a = [1, 2, 3, 4], limit 7- [1,2,3] prod 6 < 7
- *4 → 24, shrink to [4] prod 4
Result: longest valid 3, then 1
limit 20 on mixed
a = [4, 1, 9, 1], limit 20- [4,1] prod 4
- *9 → 36, drop 4 → 9
- *1 → 9 on [1,9,1]
Result: prod 9 length 3
Try it
Write longestProdUnder(a, limit). a is an array of positive integers. limit is a positive integer. L is the left index. R is the right index. The window includes a[L..R]. Valid means prod < limit. Return the longest valid length. Trace [1, 2, 3, 4] for 10 and 7, then [4, 1, 9, 1] limit 20.
All values are positive integers. limit is a positive integer. Every a[i] is < limit so a one-cell window is always valid.