|
| 1 | +//Solution taken from Leetcode's solution section |
| 2 | +//The answer is simple the only tricky thing is the ans+=right-left+1; because of which I got stuck |
| 3 | +//Here's an amazing explanation for that | taken form https://leetcode.com/problems/subarray-product-less-than-k/solution/348324 |
| 4 | +//Say, if we have an array nums = [10,5,2,6] and k = 100 |
| 5 | +//At first, we have window with 10 so ans = 0+1 and product will be 10 |
| 6 | +//After that we will move the window since product<k so ans+=right-left+1 tells us the total number of possible outcomes |
| 7 | +//How?? See we have 5 as the new value. So, the new possible subarrays are [5] and [10,5] which is right-left+1 (1-0+1 == 2) |
| 8 | +//Similarly you can see this pattern further (try it yourself or see the linked comment for more details) |
| 9 | +classSolution { |
| 10 | +publicintnumSubarrayProductLessThanK(int[]nums,intk) { |
| 11 | +if (k<=1)return0; |
| 12 | +intleft =0; |
| 13 | +intproduct =1; |
| 14 | +intans =0; |
| 15 | +for (intright =0;right<nums.length;right++) { |
| 16 | +product *=nums[right]; |
| 17 | +while (product>=k)product/=nums[left++]; |
| 18 | +ans +=right-left+1; |
| 19 | + } |
| 20 | +returnans; |
| 21 | + } |
| 22 | +} |