aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--range_sum_sorted_subarr.c37
-rw-r--r--range_sum_sorted_subarr.py61
2 files changed, 98 insertions, 0 deletions
diff --git a/range_sum_sorted_subarr.c b/range_sum_sorted_subarr.c
new file mode 100644
index 0000000..260beb8
--- /dev/null
+++ b/range_sum_sorted_subarr.c
@@ -0,0 +1,37 @@
+// 1508. Range Sum of Sorted Subarray Sums
+#include "leetcode.h"
+
+/*
+ * you are given the array 'nums' consisting of 'n' positive integers. you
+ * computed the sum of all non empty continuous subarrays from the array and
+ * then sorted them in non decreasing order, creating a new array of 'n * (n +
+ * 1) / 2' numbers. return the sum of the numbers from index 'left' to index
+ * 'right' inclusive, in the new array. since the answer may be very large,
+ * return it modulo 1e9+7
+ */
+
+int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; }
+
+int rangeSum(int *nums, int numsSize, int n, int left, int right) {
+ int size = n * (n + 1) / 2, cnt = 0, idx = 0, mod = 1e9 + 7;
+ int *arr = (int *)malloc(size * sizeof(int));
+ for (int i = 0; i < numsSize; i++) {
+ cnt = 0;
+ for (int j = i; j < numsSize; j++) {
+ cnt += nums[j];
+ arr[idx++] = cnt;
+ }
+ }
+ qsort(arr, size, sizeof(int), cmp);
+ long long ans = 0;
+ for (int i = left - 1; i < right; i++)
+ ans = (ans + arr[i]) % mod;
+ return ans;
+}
+
+int main() {
+ int n1[] = {1, 2, 3, 4}, n2[] = {1, 2, 3, 4}, n3[] = {1, 2, 3, 4};
+ printf("%d\n", rangeSum(n1, ARRAY_SIZE(n1), 4, 1, 5)); // expect: 13
+ printf("%d\n", rangeSum(n2, ARRAY_SIZE(n2), 4, 3, 4)); // expect: 6
+ printf("%d\n", rangeSum(n3, ARRAY_SIZE(n3), 4, 1, 10)); // expect: 50
+}
diff --git a/range_sum_sorted_subarr.py b/range_sum_sorted_subarr.py
new file mode 100644
index 0000000..81e28ce
--- /dev/null
+++ b/range_sum_sorted_subarr.py
@@ -0,0 +1,61 @@
+# 1508. Range Sum of Sorted Subarray Sums
+
+"""
+you are given the array 'nums' consisting of 'n' positive integers. you
+computed the sum of all non empty continuous subarrays from the array and
+then sorted them in non decreasing order, creating a new array of 'n (n +
+1) / 2' numbers. return the sum of the numbers from index 'left' to index
+'right' inclusive, in the new array. since the answer may be very large,
+return it modulo 1e9+7
+"""
+
+
+class Solution(object):
+ def rangeSum(self, nums, n, left, right):
+ """
+ :type nums: List[int]
+ :type n: int
+ :type left: int
+ :type right: int
+ :rtype: int
+ """
+ b, c = [0] * (n + 1), [0] * (n + 1)
+ for i in range(n):
+ b[i + 1] = b[i] + nums[i]
+ c[i + 1] = c[i] + b[i + 1]
+
+ def cnt_sum_und(score):
+ res, i = 0, 0
+ for j in range(n + 1):
+ while b[j] - b[i] > score:
+ i += 1
+ res += j - i
+ return res
+
+ def kth_score(k):
+ l, r = 0, b[n]
+ while l < r:
+ m = (l + r) / 2
+ if cnt_sum_und(m) < k:
+ l = m + 1
+ else:
+ r = m
+ return l
+
+ def sum_k_sums(k):
+ score = kth_score(k)
+ res, i = 0, 0
+ for j in range(n + 1):
+ while b[j] - b[i] > score:
+ i += 1
+ res += b[j] * (j - i + 1) - (c[j] - (c[i - 1] if i else 0))
+ return res - (cnt_sum_und(score) - k) * score
+
+ return sum_k_sums(right) - sum_k_sums(left - 1)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.rangeSum(nums=[1, 2, 3, 4], n=4, left=1, right=5))
+ print(obj.rangeSum(nums=[1, 2, 3, 4], n=4, left=3, right=4))
+ print(obj.rangeSum(nums=[1, 2, 3, 4], n=4, left=1, right=10))