Number of Subarrays Having Even Product - Solution & Explanation

Problem Overview: Given an integer array, count how many subarrays have an even product. A product becomes even as soon as the subarray contains at least one even number. The task is to efficiently count all such subarrays without explicitly computing every product.

Approach 1: Brute Force Enumeration (O(n²) time, O(1) space)

Generate every possible subarray using two nested loops. For each starting index i, extend the subarray to every j ≥ i and maintain the running product or simply check if any element in the window is even. Once an even number appears, every further extension of that subarray will also have an even product. This approach is straightforward but inefficient for large arrays because it inspects O(n²) subarrays.

Approach 2: Single Pass Counting (O(n) time, O(1) space)

The key observation: a subarray has an even product if it contains at least one even number. Instead of counting even-product subarrays directly, track how many subarrays consist entirely of odd numbers. While iterating through the array, maintain the length of the current streak of odd values. If the current element is odd, extend the streak and add it to the count of odd-only subarrays. When an even number appears, the streak resets to zero.

After processing the array, compute the total number of subarrays using n * (n + 1) / 2. Subtract the number of all-odd subarrays from this total. The remainder represents subarrays containing at least one even number, which guarantees an even product. This works because parity determines the product’s parity; multiplication with any even value always produces an even result.

This approach scans the array once and uses only a few counters, giving linear performance. It relies purely on parity checks rather than multiplication, making it both faster and numerically safe. The logic fits naturally with common array iteration patterns and leverages a simple observation from math about even and odd numbers. The incremental counting pattern also resembles techniques used in lightweight dynamic programming where a running state summarizes previous elements.

Recommended for interviews: Interviewers expect the single-pass approach. Brute force demonstrates you understand the problem space, but recognizing the parity property and counting odd-only segments shows stronger problem-solving skills and leads to the optimal O(n) solution.