1524. Number of Sub-arrays With Odd Sum

/**
 * Problem: LeetCode 1524 - Number of Sub-arrays With Odd Sum
 * Difficulty: Medium
 * Language: Java
 * Author: CodeByTushu
 */

class Solution {
    public int numOfSubarrays(int[] arr) {
        final int MOD = 1_000_000_007;

        int odd = 0;      // ab tak kitne prefix sums odd the
        int even = 1;     // empty prefix (sum 0) even hai
        int prefix = 0;   // current prefix sum ki parity (0 = even, 1 = odd)
        long ans = 0;

        for (int x : arr) {
            prefix = (prefix + x) % 2;

            if (prefix == 1) {
                // odd prefix - even prefix = odd sum
                ans += even;
                odd++;
            } else {
                // even prefix - odd prefix = odd sum
                ans += odd;
                even++;
            }

            ans %= MOD;
        }

        return (int) ans;
    }
}

"""
Problem: LeetCode 1524 - Number of Sub-arrays With Odd Sum
Difficulty: Medium
Language: Python 3
Author: CodeByTushu
"""

from typing import List


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        MOD = 1_000_000_007

        odd = 0
        even = 1
        prefix = 0
        ans = 0

        for x in arr:
            prefix = (prefix + x) % 2

            if prefix == 1:
                ans += even
                odd += 1
            else:
                ans += odd
                even += 1

            ans %= MOD

        return ans

/**
 * Problem: LeetCode 1524 - Number of Sub-arrays With Odd Sum
 * Difficulty: Medium
 * Language: C++
 * Author: CodeByTushu
 */

#include <vector>

class Solution {
public:
    int numOfSubarrays(std::vector<int>& arr) {
        const int MOD = 1'000'000'007;

        int odd = 0;
        int even = 1;
        int prefix = 0;
        long long ans = 0;

        for (int x : arr) {
            prefix = (prefix + x) % 2;

            if (prefix == 1) {
                ans += even;
                odd++;
            } else {
                ans += odd;
                even++;
            }

            ans %= MOD;
        }

        return static_cast<int>(ans);
    }
};

/**
 * Problem: LeetCode 1524 - Number of Sub-arrays With Odd Sum
 * Difficulty: Medium
 * Language: JavaScript
 * Author: CodeByTushu
 */

/**
 * @param {number[]} arr
 * @return {number}
 */
var numOfSubarrays = function(arr) {
    const MOD = 1_000_000_007;

    let odd = 0;
    let even = 1;
    let prefix = 0;
    let ans = 0;

    for (const x of arr) {
        prefix = (prefix + x) % 2;

        if (prefix === 1) {
            ans = (ans + even) % MOD;
            odd++;
        } else {
            ans = (ans + odd) % MOD;
            even++;
        }
    }

    return ans;
};