Number of Sub-arrays With Odd Sum - Practice Coding Problems

Number of Sub-arrays With Odd Sum - Problem

Given an array of integers arr, return the number of subarrays with an odd sum.

A subarray is a contiguous part of an array. Since the answer can be very large, return it modulo 10⁹ + 7.

Input & Output

Example 1 — Basic Case

$ Input: arr = [1,3,5]

› Output: 4

💡 Note: All odd-sum subarrays: [1] (sum=1), [3] (sum=3), [5] (sum=5), and [1,3,5] (sum=9). Total count = 4.

Example 2 — Mixed Numbers

$ Input: arr = [2,4,6]

› Output: 0

💡 Note: All elements are even, so any subarray sum will be even. No subarrays have odd sum.

Example 3 — Single Element

$ Input: arr = [1]

› Output: 1

💡 Note: Only one subarray [1] with sum=1 (odd). Count = 1.

Constraints

1 ≤ arr.length ≤ 10⁵
0 ≤ arr[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array of integers [1,3,5]

Identify Odd Subarrays

Find all contiguous subarrays with odd sum

Count Result

Return total count modulo 10^9 + 7

Key Takeaway

🎯 Key Insight: Use prefix sum parity - different parity prefix sums create odd-sum subarrays

Asked in

G Google 25 f Facebook 20 a Amazon 15 M Microsoft 12

The key insight is that a subarray has an odd sum if and only if its starting and ending prefix sums have different parities. By tracking counts of odd and even prefix sums encountered, we can count valid subarrays in O(n) time. Best approach uses prefix sum parity counting. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Running Sum	O(n²)	O(1)	Calculate sums incrementally to avoid redundant calculations
Optimal - Prefix Sum Pattern	O(n)	O(1)	Use the mathematical property that odd sums come from different parity prefix sums
Brute Force - Check All Subarrays	O(n³)	O(1)	Generate all possible subarrays and count those with odd sums

Optimized - Running Sum — Algorithm Steps

Step 1: For each starting index i
Step 2: Initialize running sum to 0
Step 3: Extend subarray and update running sum incrementally

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Position

Fix starting index and initialize running sum

Extend Incrementally

Add next element to running sum

Check Odd Sum

Count if current running sum is odd

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* arr, int n) {
    int MOD = 1000000007;
    long long count = 0;
    
    for (int i = 0; i < n; i++) {
        long long runningSum = 0;
        for (int j = i; j < n; j++) {
            runningSum += arr[j];
            if (runningSum % 2 == 1) {
                count = (count + 1) % MOD;
            }
        }
    }
    
    return count;
}

int main() {
    char line[100000];
    fgets(line, sizeof(line), stdin);
    
    int arr[10000];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        arr[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(arr, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Two nested loops: n starting positions × n ending positions, no inner sum calculation

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables for count, running sum, and loop indices

✓ Linear Space

78.0K Views

Medium Frequency

~25 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized - Running Sum — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler