Number of Subarrays Having Even Product - Practice Coding Problems

Number of Subarrays Having Even Product - Problem

Given a 0-indexed integer array nums, return the number of subarrays of nums having an even product.

A subarray is a contiguous non-empty sequence of elements within an array. The product of a subarray is even if it contains at least one even number.

Input & Output

Example 1 — Mixed Even/Odd

$ Input: nums = [2,1,4,3,6]

› Output: 13

💡 Note: Total subarrays: 15. Odd-only subarrays: [1] and [3] = 2. Even product subarrays: 15 - 2 = 13

Example 2 — All Odd

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

› Output: 0

💡 Note: All numbers are odd, so no subarray can have an even product. Result is 0

Example 3 — All Even

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

› Output: 6

💡 Note: All subarrays contain at least one even number, so all 6 subarrays have even product

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array with mix of even and odd numbers

Identify Pattern

Find odd-only segments vs subarrays containing even numbers

Count Result

Total subarrays minus odd-only subarrays

Key Takeaway

🎯 Key Insight: Count what you DON'T want (odd-only subarrays) and subtract from total

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is that it's easier to count subarrays with ALL odd numbers and subtract from total. Best approach uses mathematical counting: total subarrays n×(n+1)/2 minus odd-only subarrays. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Count Odd-Only Subarrays	O(n)	O(1)	Count subarrays with all odd numbers, subtract from total
Brute Force - Check All Subarrays	O(n³)	O(1)	Generate every possible subarray and check if product is even

Count Odd-Only Subarrays — Algorithm Steps

Calculate total possible subarrays: n*(n+1)/2
Find consecutive segments of odd numbers
For each odd segment of length k, add k*(k+1)/2 odd-only subarrays
Return total subarrays minus odd-only subarrays

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Odd Segments

Identify consecutive runs of odd numbers

Calculate Combinations

For each odd segment, count possible subarrays

Subtract

Total subarrays minus odd-only subarrays

Code -

solution.c — C

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

int solution(int* nums, int numsSize) {
    int n = numsSize;
    int totalSubarrays = n * (n + 1) / 2;
    
    int oddOnlySubarrays = 0;
    int oddLength = 0;
    
    for (int i = 0; i < n; i++) {
        if (nums[i] % 2 == 1) { // odd number
            oddLength++;
        } else { // even number
            if (oddLength > 0) {
                oddOnlySubarrays += oddLength * (oddLength + 1) / 2;
                oddLength = 0;
            }
        }
    }
    
    // Handle remaining odd sequence at end
    if (oddLength > 0) {
        oddOnlySubarrays += oddLength * (oddLength + 1) / 2;
    }
    
    return totalSubarrays - oddOnlySubarrays;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int nums[1000];
    int size = 0;
    char *token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            nums[size++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(nums, size);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array to identify odd segments

✓ Linear Growth

Space Complexity

O(1)

Only using variables for counting and tracking

✓ Linear Space

12.0K Views

Medium Frequency

~15 min Avg. Time

450 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

Count Odd-Only Subarrays — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler