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.

Description Hints 3 Solution Video 9:56

2495. Number of Subarrays Having Even Product

Medium63.2% acceptancePremium elsewhere, free here

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 <= 10⁵
1 <= nums[i] <= 10⁵

Topics

Hints open one at a time

Hint 1

The product of elements in a subarray is even if it contains at least one even element.

Hint 2

Iterate from left to right and save the last index of an even number. Let that saved index be “j”.

Hint 3

It can be seen that every subarray starting from earlier than index “j” and ending at the current index has an even product.

9:56

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[9,6,7,13]

Input

[7,3,5]

Your code is saved on this device.Solution