Formatted question description: https://leetcode.ca/all/713.html
Level
Medium
Description
You are given an array of positive integers nums.
Count and print the number of (contiguous) subarrays where the product of all the elements in the subarray is less than k.
Example 1:
Input: nums = [10, 5, 2, 6], k = 100
Output: 8
Explanation: The 8 subarrays that have product less than 100 are: [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6].
Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.
Note:
0 < nums.length <= 50000.0 < nums[i] < 1000.0 <= k < 10^6.
Solution
Initialize product = 1, count = 0, start = 0 and end = 0. Loop over nums using end as the index. Each time let product *= nums[end]. If product >= k, then do product /= nums[start++] until product < k. Then calculate the length of the current subarray, which is end - start + 1. The length of the current subarray is also the number of subarrays with product less than k and ends at index end. Add the length of the current subarray to count. Finally, return count.
Java Code
public class Subarray_Product_Less_Than_K {
public static void main(String[] args) {
Subarray_Product_Less_Than_K out = new Subarray_Product_Less_Than_K();
Solution s = out.new Solution();
System.out.println(s.numSubarrayProductLessThanK(new int[]{10, 5, 2, 6}, 100));
}
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
if (k == 0) {
return 0;
}
// log transformation: log(a*b) = log(a) + log(b)
double logk = Math.log(k);
double[] prefix = new double[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
prefix[i+1] = prefix[i] + Math.log(nums[i]);
}
int count = 0;
for (int i = 0; i < prefix.length; i++) {
int lo = i + 1, hi = prefix.length;
while (lo < hi) {
int mi = lo + (hi - lo) / 2;
if (prefix[mi] < prefix[i] + logk - 1e-9) {
lo = mi + 1;
} else {
hi = mi;
}
}
count += lo - i - 1;
}
return count;
}
}
// this is just a flip, instead of compare for <k, to compare >=k then count.
// I don't like this one, seems hack. Will still fail according to input
// what if test case is [9,9,9, ... ,9] (many) and k=1
class Solution_ACed {
public int numSubarrayProductLessThanK(int[] nums, int k) {
if (k < 2) {
return 0;
}
int result = 0;
int product = 1;
for (int i = 0, right = 0; right < nums.length; right++) {
product *= nums[right];
while (i < nums.length && product >= k) {
product /= nums[i++];
}
result += right - i + 1;
}
return result;
}
}
/*
failed by:
nums=[1,1,1,1,1, ... ,1] (billion 1s)
k=9
*/
class Solution_wrong {
public int numSubarrayProductLessThanK(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return 0;
}
int count = 0;
int left = 0;
// basic idea, moving right to right direction, if current multiple is >= k , then no need to go right further
// assumption: all positive
// variation of this question, what if there is 0, or negative numbers
while (left < nums.length) {
int current = 1;
int right = left;
// @note: possible overflow from * operation
while (right < nums.length && current * nums[right] < k) { // will stop if current >= k
count++;
current *= nums[right];
right++;
}
left++;
}
return count;
}
}
}Java
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
if (nums == null || nums.length == 0 || k <= 1)
return 0;
int product = 1;
int count = 0;
int start = 0, end = 0;
int length = nums.length;
while (end < length) {
product *= nums[end];
while (product >= k) {
product /= nums[start];
start++;
}
count += end - start + 1;
end++;
}
return count;
}
}