Subarrays with Small Product
Count the contiguous subarrays whose element product is strictly less than K. All values are positive.
Input: the first line has N and K; the second line has N positive integers.
Output: the number of subarrays with product < K.
Constraints:
- 1 ≤ N ≤ 105
- 1 ≤ ai ≤ 1000
- 1 ≤ K ≤ 109
Sample Tests
Input 1
4 10 1 2 3 4
Output 1
7
Input 2
3 1 5 6 7
Output 2
0
Discussion (opens after you solve — no spoilers before)
No comments yet.