aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--count_subarr_score_less_k.c26
-rw-r--r--count_subarr_score_less_k.py31
2 files changed, 57 insertions, 0 deletions
diff --git a/count_subarr_score_less_k.c b/count_subarr_score_less_k.c
new file mode 100644
index 0000000..5c454d1
--- /dev/null
+++ b/count_subarr_score_less_k.c
@@ -0,0 +1,26 @@
+// 2302. Count Subarrays With Score Less Than K
+#include "leetcode.h"
+
+/*
+ * 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'. a
+ * subarray is a contiguous sequence of elements within an array.
+ */
+
+long long countSubarrays(int *nums, int numsSize, long long k) {
+ long long ans = 0, curr = 0;
+ for (int j = 0, i = 0; j < numsSize; ++j) {
+ curr += nums[j];
+ while (curr * (j - i + 1) >= k)
+ curr -= nums[i++];
+ ans += j - i + 1;
+ }
+ return ans;
+}
+
+int main() {
+ int n1[] = {2, 1, 4, 3, 5}, n2[] = {1, 1, 1};
+ printf("%lld\n", countSubarrays(n1, ARRAY_SIZE(n1), 10)); // expect: 6
+ printf("%lld\n", countSubarrays(n2, ARRAY_SIZE(n2), 5)); // expect: 5
+}
diff --git a/count_subarr_score_less_k.py b/count_subarr_score_less_k.py
new file mode 100644
index 0000000..d60cb4b
--- /dev/null
+++ b/count_subarr_score_less_k.py
@@ -0,0 +1,31 @@
+# 2302. Count Subarrays With Score Less Than K
+
+"""
+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'. a
+subarray is a contiguous sequence of elements within an array.
+"""
+
+
+class Solution(object):
+ def countSubarrays(self, nums, k):
+ """
+ :type nums: List[int]
+ :type k: int
+ :rtype: int
+ """
+ ans, curr, i = 0, 0, 0
+ for j in range(len(nums)):
+ curr += nums[j]
+ while curr * (j - i + 1) >= k:
+ curr -= nums[i]
+ i += 1
+ ans += j - i + 1
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.countSubarrays(nums=[2, 1, 4, 3, 5], k=10))
+ print(obj.countSubarrays(nums=[1, 1, 1], k=5))