1524. Number of Sub-arrays With Odd Sum LeetCode Solution
In this guide, you will get 1524. Number of Sub-arrays With Odd Sum LeetCode Solution with the best time and space complexity. The solution to Number of Sub-arrays With Odd Sum problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Number of Sub-arrays With Odd Sum
Given an array of integers arr, return the number of subarrays with an odd sum.
Since the answer can be very large, return it modulo 109 + 7.
Example 1:
Input: arr = [1,3,5]
Output: 4
Explanation: All subarrays 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 subarrays 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
Constraints:
1 <= arr.length <= 105
1 <= arr[i] <= 100
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
1524. Number of Sub-arrays With Odd Sum LeetCode Solution in C++
class Solution {
public:
int numOfSubarrays(vector<int>& arr) {
constexpr int kMod = 1'000'000'007;
const int n = arr.size();
long ans = 0;
// dp0[i] := the number of subarrays that end in arr[i - 1] with an even sum
vector<int> dp0(n + 1);
// dp1[i] := the number of subarrays that end in arr[i - 1] with an odd sum
vector<int> dp1(n + 1);
for (int i = 1; i <= n; ++i) {
if (arr[i - 1] % 2 == 1) {
dp0[i] = dp1[i - 1];
dp1[i] = dp0[i - 1] + 1;
} else {
dp0[i] = dp0[i - 1] + 1;
dp1[i] = dp1[i - 1];
}
ans = (ans + dp1[i]) % kMod;
}
return ans;
}
}; /* code provided by PROGIEZ */
1524. Number of Sub-arrays With Odd Sum LeetCode Solution in Java
class Solution {
public:
int numOfSubarrays(vector<int>& arr) {
constexpr int kMod = 1'000'000'007;
long ans = 0;
long dp0 = 0;
long dp1 = 0;
for (const int a : arr) {
if (a % 2 == 1) {
const int cache = dp0;
dp0 = dp1;
dp1 = cache + 1;
} else {
++dp0;
}
ans = (ans + dp1) % kMod;
}
return ans;
}
}; // code provided by PROGIEZ
1524. Number of Sub-arrays With Odd Sum LeetCode Solution in Python
