Subarray Product Less Than K
This program counts subarrays with product less than K.
Problem Statement
Write a Java program to count subarrays with product less than 100.
Source Code
| 1 | public class SubarrayProductLessThanK { |
| 2 | public static void main(String[] args) { |
| 3 | System.out.println("Eduinq Subarray Product Less Than K"); |
| 4 | int[] arr = {10,5,2,6}; |
| 5 | int k=100, prod=1, count=0, left=0; |
| 6 | for(int right=0;right<arr.length;right++){ |
| 7 | prod*=arr[right]; |
| 8 | while(prod>=k && left<=right){ |
| 9 | prod/=arr[left++]; |
| 10 | } |
| 11 | count+=right-left+1; |
| 12 | } |
| 13 | System.out.println("Total subarrays with product < "+k+" = "+count); |
| 14 | } |
| 15 | } |
Program Output
Eduinq Subarray Product Less Than K Total subarrays with product < 100 = 8
Explanation
A sliding window maintains the running product of the current window, and whenever the product reaches or exceeds k, the left pointer shifts forward dividing out elements, with the count of valid subarrays accumulated for every valid window.