Welcome to Subscribe On Youtube
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; } } } ############ class Solution { public int numSubarrayProductLessThanK(int[] nums, int k) { int ans = 0; for (int i = 0, j = 0, s = 1; i < nums.length; ++i) { s *= nums[i]; while (j <= i && s >= k) { s /= nums[j++]; } ans += i - j + 1; } return ans; } }
-
// OJ: https://leetcode.com/problems/subarray-product-less-than-k/ // Time: O(N) // Space: O(1) class Solution { public: int numSubarrayProductLessThanK(vector<int>& A, int k) { if (k == 0) return 0; long i = 0, j = 0, N = A.size(), prod = 1, ans = 0; for (; j < N; ++j) { prod *= A[j]; while (i <= j && prod >= k) prod /= A[i++]; ans += j - i + 1; } return ans; } };
-
class Solution: def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int: ans, s, j = 0, 1, 0 for i, v in enumerate(nums): s *= v while j <= i and s >= k: s //= nums[j] j += 1 ans += i - j + 1 return ans ############ class Solution(object): def numSubarrayProductLessThanK(self, nums, k): N = len(nums) # 数组/字符串长度 left, right = 0, 0 # 双指针,表示当前遍历的区间[left, right],闭区间 prods = 1 # 用于统计 子数组/子区间 是否有效,根据题目可能会改成求和/计数/乘积 res = 0 # 保存最大的满足题目要求的 子数组/子串 长度 while right < N: # 当右边的指针没有搜索到 数组/字符串 的结尾 prods *= nums[right] # 增加当前右边指针的数字/字符的求和/计数 while prods >= k and left <= right: # 此时需要一直移动左指针,直至找到一个符合题意的区间 prods /= nums[left] # 移动左指针前需要从counter中减少left位置字符的求和/计数 left += 1 # 真正的移动左指针,注意不能跟上面一行代码写反 # 到 while 结束时,我们找到了一个符合题意要求的 子数组/子串 res += right - left + 1 # 需要更新结果 right += 1 # 移动右指针,去探索新的区间 return res
-
func numSubarrayProductLessThanK(nums []int, k int) int { ans := 0 for i, j, s := 0, 0, 1; i < len(nums); i++ { s *= nums[i] for ; j <= i && s >= k; j++ { s /= nums[j] } ans += i - j + 1 } return ans }
-
function numSubarrayProductLessThanK(nums: number[], k: number): number { let ans = 0; for (let i = 0, j = 0, s = 1; i < nums.length; ++i) { s *= nums[i]; while (j <= i && s >= k) { s /= nums[j++]; } ans += i - j + 1; } return ans; }
-
/** * @param {number[]} nums * @param {number} k * @return {number} */ var numSubarrayProductLessThanK = function (nums, k) { const n = nums.length; let ans = 0; let s = 1; for (let i = 0, j = 0; i < n; ++i) { s *= nums[i]; while (j <= i && s >= k) { s = Math.floor(s / nums[j++]); } ans += i - j + 1; } return ans; };
-
impl Solution { pub fn num_subarray_product_less_than_k(nums: Vec<i32>, k: i32) -> i32 { if k <= 1 { return 0; } let mut res = 0; let mut product = 1; let mut i = 0; nums.iter().enumerate().for_each(|(j, v)| { product *= v; while product >= k { product /= nums[i]; i += 1; } res += j - i + 1; }); res as i32 } }
-
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; } } ############ class Solution { public int numSubarrayProductLessThanK(int[] nums, int k) { int ans = 0; for (int i = 0, j = 0, s = 1; i < nums.length; ++i) { s *= nums[i]; while (j <= i && s >= k) { s /= nums[j++]; } ans += i - j + 1; } return ans; } }
-
// OJ: https://leetcode.com/problems/subarray-product-less-than-k/ // Time: O(N) // Space: O(1) class Solution { public: int numSubarrayProductLessThanK(vector<int>& A, int k) { if (k == 0) return 0; long i = 0, j = 0, N = A.size(), prod = 1, ans = 0; for (; j < N; ++j) { prod *= A[j]; while (i <= j && prod >= k) prod /= A[i++]; ans += j - i + 1; } return ans; } };
-
class Solution: def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int: ans, s, j = 0, 1, 0 for i, v in enumerate(nums): s *= v while j <= i and s >= k: s //= nums[j] j += 1 ans += i - j + 1 return ans ############ class Solution(object): def numSubarrayProductLessThanK(self, nums, k): N = len(nums) # 数组/字符串长度 left, right = 0, 0 # 双指针,表示当前遍历的区间[left, right],闭区间 prods = 1 # 用于统计 子数组/子区间 是否有效,根据题目可能会改成求和/计数/乘积 res = 0 # 保存最大的满足题目要求的 子数组/子串 长度 while right < N: # 当右边的指针没有搜索到 数组/字符串 的结尾 prods *= nums[right] # 增加当前右边指针的数字/字符的求和/计数 while prods >= k and left <= right: # 此时需要一直移动左指针,直至找到一个符合题意的区间 prods /= nums[left] # 移动左指针前需要从counter中减少left位置字符的求和/计数 left += 1 # 真正的移动左指针,注意不能跟上面一行代码写反 # 到 while 结束时,我们找到了一个符合题意要求的 子数组/子串 res += right - left + 1 # 需要更新结果 right += 1 # 移动右指针,去探索新的区间 return res
-
func numSubarrayProductLessThanK(nums []int, k int) int { ans := 0 for i, j, s := 0, 0, 1; i < len(nums); i++ { s *= nums[i] for ; j <= i && s >= k; j++ { s /= nums[j] } ans += i - j + 1 } return ans }
-
function numSubarrayProductLessThanK(nums: number[], k: number): number { let ans = 0; for (let i = 0, j = 0, s = 1; i < nums.length; ++i) { s *= nums[i]; while (j <= i && s >= k) { s /= nums[j++]; } ans += i - j + 1; } return ans; }
-
/** * @param {number[]} nums * @param {number} k * @return {number} */ var numSubarrayProductLessThanK = function (nums, k) { const n = nums.length; let ans = 0; let s = 1; for (let i = 0, j = 0; i < n; ++i) { s *= nums[i]; while (j <= i && s >= k) { s = Math.floor(s / nums[j++]); } ans += i - j + 1; } return ans; };
-
impl Solution { pub fn num_subarray_product_less_than_k(nums: Vec<i32>, k: i32) -> i32 { if k <= 1 { return 0; } let mut res = 0; let mut product = 1; let mut i = 0; nums.iter().enumerate().for_each(|(j, v)| { product *= v; while product >= k { product /= nums[i]; i += 1; } res += j - i + 1; }); res as i32 } }