LeetCode Entry
1524. Number of Sub-arrays With Odd Sum
Subarrays with odd sum
1524. Number of Sub-arrays With Odd Sum medium substack youtube
https://dmitrysamoylenko.com/leetcode/

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