Description
The score of an array is defined as the product of its sum and its length. Given a positive integer array nums and an integer k, return the number of non-empty subarrays of nums whose score is strictly less than k.
Examples
Input:
nums = [2,1,4,3,5], k = 10Output:
6Explanation:
6 subarrays have score < 10
Input:
nums = [1,1,1], k = 5Output:
5Explanation:
The subarrays are: [1] (score=1*1=1), [1] (score=1*1=1), [1] (score=1*1=1), [1,1] (score=2*2=4), [1,1] (score=2*2=4), [1,1,1] (score=3*3=9). Since 9 ≥ 5, only the first 5 subarrays have score < 5.
Input:
nums = [3,2], k = 15Output:
3Explanation:
The subarrays are: [3] (score=3*1=3), [2] (score=2*1=2), [3,2] (score=5*2=10). All 3 subarrays have scores less than 15, so the answer is 3.
Constraints
- •
1 ≤ nums.length ≤ 10^5 - •
1 ≤ nums[i] ≤ 10^5 - •
1 ≤ k ≤ 10^15