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^51 <= 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 |
class Solution { public: int numOfSubarrays(vector<int>& arr) { const int n = arr.size(); constexpr int kMod = 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. vector<vector<int>> dp(n + 1, vector<int>(2)); long ans = 0; for (int i = 1; i <= n; ++i) { if (arr[i - 1] & 1) { dp[i][0] = dp[i - 1][1]; dp[i][1] = dp[i - 1][0] + 1; } else { dp[i][0] = dp[i - 1][0] + 1; dp[i][1] = dp[i - 1][1]; } ans += dp[i][1]; } return ans % kMod; } }; |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua class Solution { public int numOfSubarrays(int[] arr) { long ans = 0, odd = 0, even = 0; for (int x : arr) { even += 1; if (x % 2 == 1) { long t = even; even = odd; odd = t; } ans += odd; } return (int)(ans % (int)(1e9 + 7)); } } |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 |
# Author: Huahua class Solution: def numOfSubarrays(self, arr: List[int]) -> int: ans, odd, even = 0, 0, 0 for x in arr: if x & 1: odd, even = even + 1, odd else: odd, even = odd, even + 1 ans += odd return ans % int(1e9 + 7) |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment