Package g2301_2400.s2302_count_subarrays_with_score_less_than_k

Class Solution

java.lang.Object

g2301_2400.s2302_count_subarrays_with_score_less_than_k.Solution

public class Solution
extends Object

2302 - Count Subarrays With Score Less Than K.<p>Hard</p> <p>The <strong>score</strong> of an array is defined as the <strong>product</strong> of its sum and its length.</p> <ul> <li>For example, the score of <code>[1, 2, 3, 4, 5]</code> is <code>(1 + 2 + 3 + 4 + 5) * 5 = 75</code>.</li> </ul> <p>Given a positive integer array <code>nums</code> and an integer <code>k</code>, return <em>the <strong>number of non-empty subarrays</strong> of</em> <code>nums</code> <em>whose score is <strong>strictly less</strong> than</em> <code>k</code>.</p> <p>A <strong>subarray</strong> is a contiguous sequence of elements within an array.</p> <p><strong>Example 1:</strong></p> <p><strong>Input:</strong> nums = [2,1,4,3,5], k = 10</p> <p><strong>Output:</strong> 6</p> <p><strong>Explanation:</strong></p> <p>The 6 subarrays having scores less than 10 are:</p> <ul> <li> <p>[2] with score 2 * 1 = 2.</p> </li> <li> <p>[1] with score 1 * 1 = 1.</p> </li> <li> <p>[4] with score 4 * 1 = 4.</p> </li> <li> <p>[3] with score 3 * 1 = 3.</p> </li> <li> <p>[5] with score 5 * 1 = 5.</p> </li> <li> <p>[2,1] with score (2 + 1) * 2 = 6.</p> </li> </ul> <p>Note that subarrays such as [1,4] and [4,3,5] are not considered because their scores are 10 and 36 respectively, while we need scores strictly less than 10.</p> <p><strong>Example 2:</strong></p> <p><strong>Input:</strong> nums = [1,1,1], k = 5</p> <p><strong>Output:</strong> 5</p> <p><strong>Explanation:</strong></p> <p>Every subarray except [1,1,1] has a score less than 5.</p> <p>[1,1,1] has a score (1 + 1 + 1) * 3 = 9, which is greater than 5.</p> <p>Thus, there are 5 subarrays having scores less than 5.</p> <p><strong>Constraints:</strong></p> <ul> <li><code>1 <= nums.length <= 10⁵</code></li> <li><code>1 <= nums[i] <= 10⁵</code></li> <li><code>1 <= k <= 10¹⁵</code></li> </ul>

Constructor Summary

Constructors

Constructor	Description
Solution()

Method Summary

Modifier and Type	Method	Description
long	countSubarrays(int[] nums, long k)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

Solution

public Solution()

Method Details

countSubarrays

public long countSubarrays(int[] nums,
 long k)