Given an array of integers arr. Return the number of sub-arrays with odd sum.
As the answer may grow large, the answer must be computed modulo 10^9 + 7.
Example 1:
Input: arr = [1,3,5]
Output: 4
Explanation: All sub-arrays are [[1],[1,3],[1,3,5],[3],[3,5],[5]]
All sub-arrays sum are [1,4,9,3,8,5].
Odd sums are [1,9,3,5] so the answer is 4.
Example 2:
Input: arr = [2,4,6]
Output: 0
Explanation: All sub-arrays are [[2],[2,4],[2,4,6],[4],[4,6],[6]]
All sub-arrays sum are [2,6,12,4,10,6].
All sub-arrays have even sum and the answer is 0.
Example 3:
Input: arr = [1,2,3,4,5,6,7]
Output: 16
Example 4:
Input: arr = [100,100,99,99]
Output: 4
Example 5:
Input: arr = [7]
Output: 1
Constraints:
1 <= arr.length <= 10^5
1 <= arr[i] <= 100
Solution: DP
We would like to know how many subarrays end with arr[i] have odd or even sums.
dp[i][0] := # end with arr[i] has even sum dp[i][1] := # end with arr[i] has even sum
if arr[i] is even:
dp[i][0]=dp[i-1][0] + 1, dp[i][1]=dp[i-1][1]
else:
dp[i][1]=dp[i-1][0], dp[i][0]=dp[i-1][0] + 1
ans = sum(dp[i][1])
Time complexity: O(n) Space complexity: O(n) -> O(1)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
classSolution{
public:
intnumOfSubarrays(vector<int>& arr) {
const int n = arr.size();
constexprintkMod=1e9+7;
// dp[i][0] # of subarrays ends with a[i-1] have even sums.
// dp[i][1] # of subarrays ends with a[i-1] have odd sums.
Given the array nums consisting of n positive integers. You computed the sum of all non-empty continous subarrays from the array and then sort 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 (indexed from 1), inclusive, in the new array. Since the answer can be a huge number return it modulo 10^9 + 7.
Example 1:
Input: nums = [1,2,3,4], n = 4, left = 1, right = 5
Output: 13
Explanation: All subarray sums are 1, 3, 6, 10, 2, 5, 9, 3, 7, 4. After sorting them in non-decreasing order we have the new array [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. The sum of the numbers from index le = 1 to ri = 5 is 1 + 2 + 3 + 3 + 4 = 13.
Example 2:
Input: nums = [1,2,3,4], n = 4, left = 3, right = 4
Output: 6
Explanation: The given array is the same as example 1. We have the new array [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. The sum of the numbers from index le = 3 to ri = 4 is 3 + 3 = 6.
Example 3:
Input: nums = [1,2,3,4], n = 4, left = 1, right = 10
Output: 50
Constraints:
1 <= nums.length <= 10^3
nums.length == n
1 <= nums[i] <= 100
1 <= left <= right <= n * (n + 1) / 2
Solution 1: Brute Force
Find sums of all the subarrays and sort the values.
Time complexity: O(n^2logn) Space complexity: O(n^2)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
// Author: Huahua
classSolution{
public:
intrangeSum(vector<int>& nums, int n, int left, int right) {
For each subarray, start with one element e.g nums[i], put them into a priority queue (min heap). Each time, we have the smallest subarray sum, and extend that subarray and put the new sum back into priority queue. Thought it has the same time complexity as the brute force one in worst case, but space complexity can be reduce to O(n).
Time complexity: O(n^2logn) Space complexity: O(n)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
structEntry{
intsum;
inti;
booloperator<(constEntry& e) const { return sum > e.sum;}
};
classSolution{
public:
intrangeSum(vector<int>& nums, int n, int left, int right) {
constexpr int kMod = 1e9 + 7;
priority_queue<Entry>q;// Sort by e.sum in descending order.