Skip to main content
Talentd

Number of Subarrays Having Even Product - Solution & Explanation

MediumPremiumFree on FleetCodeArrayMathDynamic Programming5 min read
Practice this problem

Problem Statement

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

 

Example 1:

Input: nums = [9,6,7,13]
Output: 6
Explanation: There are 6 subarrays with an even product:
- nums[0..1] = 9 * 6 = 54.
- nums[0..2] = 9 * 6 * 7 = 378.
- nums[0..3] = 9 * 6 * 7 * 13 = 4914.
- nums[1..1] = 6.
- nums[1..2] = 6 * 7 = 42.
- nums[1..3] = 6 * 7 * 13 = 546.

Example 2:

Input: nums = [7,3,5]
Output: 0
Explanation: There are no subarrays with an even product.

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105

Approach Overview

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(n2) 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(n2) 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.

Solution

We know that the product of a subarray is even if and only if there is at least one even number in the subarray.

Therefore, we can traverse the array, record the index last of the most recent even number, then the number of subarrays ending with the current element and having an even product is last + 1. We can add this to the result.

The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Subarray EnumerationO(n²)O(1)Small arrays or when first exploring the problem during interviews
Single Pass Odd-Streak CountingO(n)O(1)General case and optimal solution expected in coding interviews

Video Solution

leetcode 2495. Number of Subarrays Having Even Product - check last seen even number's index • Code-Yao • 176 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Number of Subarrays Having Even Product easy or hard?
The problem is rated Medium because the brute force idea is simple but inefficient. The challenge is recognizing the parity insight that any subarray containing an even number automatically has an even product, which enables an O(n) counting solution.
Number of Subarrays Having Even Product Python/Java solution
Most implementations use a single loop. Maintain an integer tracking the current streak of odd numbers and another for the total odd-only subarrays. After processing the array, compute total subarrays and subtract the odd-only count. The same logic translates directly to Python, Java, C++, and Go.
How to solve Number of Subarrays Having Even Product in O(n)?
Iterate through the array while maintaining the length of the current sequence of odd numbers. Each odd value extends the streak and contributes to the number of odd-only subarrays. When an even value appears, reset the streak. Compute total subarrays using n*(n+1)/2 and subtract the odd-only count to obtain the number of even-product subarrays.
What is the best approach for Number of Subarrays Having Even Product?
The optimal approach is a single-pass counting method. Instead of directly checking every subarray, track consecutive odd elements and count subarrays that contain only odd numbers. Subtract this count from the total number of subarrays to get those with an even product. This runs in O(n) time and uses O(1) extra space.
Is Number of Subarrays Having Even Product asked at Google/Amazon/Meta?
Parity-based array counting problems appear frequently in interviews at large tech companies including Google, Amazon, and Meta. Variants involving subarray parity, prefix properties, or counting valid subarrays are common because they test pattern recognition and linear-time optimization.
What data structure is used in Number of Subarrays Having Even Product?
The solution primarily uses simple counters while iterating through an array. No advanced data structures are required. The algorithm relies on tracking consecutive odd elements and basic arithmetic to compute the final count.
What is the time complexity of Number of Subarrays Having Even Product?
The optimal algorithm runs in O(n) time because the array is scanned once while maintaining a running count of consecutive odd numbers. Space complexity is O(1) since only a few integer counters are used regardless of input size.

Ready to solve this problem?

Practice Number of Subarrays Having Even Product with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays