32. Subarray Product Less Than K
Count continuous ranges whose mathematical product is less than k. Each different start and end position describes a separate candidate.
The comparison is strictly less than, not less than or equal to. Avoid machine overflow when a growing product would exceed the supported numeric range.
Example 1
Input
nums=[10,5,2,6], k=100
Output
8
Explanation: The four singles plus [10,5], [5,2], [2,6], and [5,2,6] qualify; [10,5,2] equals the strict threshold and fails.
Example 2
Input
nums=[1,1,1], k=2
Output
6
Explanation: Every nonempty interval has product one, so all six count.
Constraints
0 <= nums.length <= 1051 <= nums[i] <= 231 - 1-263 <= k <= 263 - 1
Hints
Hint 1
For one right endpoint, which starts produce valid suffixes?
Hint 2
How can product*x<k be checked without multiplying?
Hint 3
Shrink while product>(k-1)/x, multiply safely, and add right-left+1.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Shrink before multiplying, then count valid suffixes
[10,5,2,6]
100
8