Skills101
← All coding problems

Subarrays With Product Less Than K

mediumArrays & Prefix Sums+20 XPTime limit 2s

All numbers in the array are positive. Count the contiguous subarrays whose product is strictly less than k.

Input:

  • line 1: n k
  • line 2: n positive integers

Output: the number of such subarrays (use 64-bit integers).

Constraints: 1 ≤ n ≤ 10⁵, 1 ≤ a[i] ≤ 1000, 1 ≤ k ≤ 10⁶.

Think about it: use a sliding window. Extend it to the right, multiplying the product; while the product is ≥ k, divide out the leftmost element. Every window [l..r] that survives contributes r − l + 1 subarrays ending at r. (With k ≤ 1 the answer is 0 — no product of positive integers is below 1.)

Sample input 1

4 100
10 5 2 6

Sample output 1

8

Sample input 2

3 1
1 2 3

Sample output 2

0

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.