Number of sub arrays with odd sum

Array Math Dynamic Programming Prefix Sum

55.8% acceptance

Feb 25, 2026

2066

101

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.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn num_of_subarrays(arr: Vec<i32>) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let mut ans = 0i64;
    let mut even_cnt = 1i64; // prefix sum 0 (even)
    let mut odd_cnt = 0i64;
    let mut prefix = 0i32;
    for x in arr {
      prefix = (prefix + x) % 2;
      if prefix % 2 == 0 {
        ans = (ans + odd_cnt) % MOD;
        even_cnt += 1;
      } else {
        ans = (ans + even_cnt) % MOD;
        odd_cnt += 1;
      }
    }
    ans as i32
  }
}