LeetCode Entry

1524. Number of Sub-arrays With Odd Sum

15.11.2026 medium 2026 kotlin rust

Subarrays with odd sum

1524. Number of Sub-arrays With Odd Sum medium substack youtube

https://dmitrysamoylenko.com/leetcode/

15.11.2026.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1543

Problem TLDR

Subarrays with odd sum

Intuition

    // 1110100001
    // 1000000001

Count prefix sums so far, how many are odd, how many are even. Add a new odd element. If new sum is odd then each even prefix makes odd suffix. If new sum is even then each odd prefix makes odd suffix.

Approach

  • for empty prefix we have to initialize even count = 1 (or just rundown some examples to see that)

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code

    fun numOfSubarrays(a: IntArray) =
    run{var o=0;a.foldIndexed(0){i,r,x->if(x%2>0)o=i-o+1;(r+o)%1000000007}}
    pub fn num_of_subarrays(a: Vec<i32>) -> i32 {
        let (mut o, mut s) = (0, 0);
        for x in &a { s ^= x & 1; o += s as i64 }
        (o * (a.len() as i64 + 1 - o) % 1_000_000_007) as i32
    }

Comments