Count Subarrays with Product Less Than K

You are given an array of positive integers and an integer k. Your task is to count the number of contiguous subarrays whose product is strictly less than k. Formally, for each subarray arr[l...r], you need to count it if and only if \(\prod_{i=l}^{r} arr[i] < k\).

Note: When k is less than or equal to 1, no subarray satisfies the condition.

The problem demands an efficient solution, ideally in \(O(n)\) time complexity, by using a sliding window (two pointers) technique.

inputFormat

The first line of input contains an integer T, the number of test cases. Each test case is described as follows:

• The first line contains two integers, N (the length of the array) and k.
• The second line contains N space-separated positive integers representing the array.

All input is read from standard input.

outputFormat

For each test case, output a single line containing the number of contiguous subarrays whose product is strictly less than k. The output should be printed to standard output.

1
4 10
1 2 3 4

7