count-the-subarrays-having-product-less-than-k1708.md

Count the subarrays having product less than k

Given an array of positive numbers, the task is to find the number of possible contiguous subarrays having product less than a given number k.

Sample Input

4 10
1 2 3 4

Sample Output

7

Solution

class Solution{
  public:
    int countSubArrayProductLessThanK(const vector<int>& a, int n, long long k) {
        int left = 0;
        int right = 0;
        long long prod = 1;
        int count = 0;

        for(int i = 0; i < n; ++i) {
            right = i;
            
            prod *= a[right];
            count += right - left + 1;
            
            while(prod >= k) {
                prod /= a[left++];
                count -= 1;
            }
        }
        
        return count;
    }
};

Accepted