Welcome to Subscribe On Youtube

1524. Number of Sub-arrays With Odd Sum

Description

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

Solutions

• Java
• C++
• Python
• Go
• TypeScript
• RenderScript

• class Solution {
      public int numOfSubarrays(int[] arr) {
          final int mod = (int) 1e9 + 7;
          int[] cnt = {1, 0};
          int ans = 0, s = 0;
          for (int x : arr) {
              s += x;
              ans = (ans + cnt[s & 1 ^ 1]) % mod;
              ++cnt[s & 1];
          }
          return ans;
      }
  }
  

• class Solution {
  public:
      int numOfSubarrays(vector<int>& arr) {
          const int mod = 1e9 + 7;
          int cnt[2] = {1, 0};
          int ans = 0, s = 0;
          for (int x : arr) {
              s += x;
              ans = (ans + cnt[s & 1 ^ 1]) % mod;
              ++cnt[s & 1];
          }
          return ans;
      }
  };
  

• class Solution:
      def numOfSubarrays(self, arr: List[int]) -> int:
          mod = 10**9 + 7
          cnt = [1, 0]
          ans = s = 0
          for x in arr:
              s += x
              ans = (ans + cnt[s & 1 ^ 1]) % mod
              cnt[s & 1] += 1
          return ans
  
  

• func numOfSubarrays(arr []int) (ans int) {
  	const mod int = 1e9 + 7
  	cnt := [2]int{1, 0}
  	s := 0
  	for _, x := range arr {
  		s += x
  		ans = (ans + cnt[s&1^1]) % mod
  		cnt[s&1]++
  	}
  	return
  }
  

• function numOfSubarrays(arr: number[]): number {
      let ans = 0;
      let s = 0;
      const cnt: number[] = [1, 0];
      const mod = 1e9 + 7;
      for (const x of arr) {
          s += x;
          ans = (ans + cnt[(s & 1) ^ 1]) % mod;
          cnt[s & 1]++;
      }
      return ans;
  }
  
  

• impl Solution {
      pub fn num_of_subarrays(arr: Vec<i32>) -> i32 {
          const MOD: i32 = 1_000_000_007;
          let mut cnt = [1, 0];
          let mut ans = 0;
          let mut s = 0;
          for &x in arr.iter() {
              s += x;
              ans = (ans + cnt[((s & 1) ^ 1) as usize]) % MOD;
              cnt[(s & 1) as usize] += 1;
          }
          ans
      }
  }
  
  

All Problems

All Solutions