Problem Description

You are given a 0-indexed integer array nums. Your task is to count how many subarrays of nums have an even product.

A subarray is a contiguous sequence of elements from the array. The product of a subarray is the result of multiplying all elements within that subarray together. A product is even if it's divisible by 2.

For example, if nums = [1, 2, 3]:

• Subarray [1] has product 1 (odd)
• Subarray [2] has product 2 (even)
• Subarray [3] has product 3 (odd)
• Subarray [1, 2] has product 2 (even)
• Subarray [2, 3] has product 6 (even)
• Subarray [1, 2, 3] has product 6 (even)

So there are 4 subarrays with even products.

The key insight is that a product is even if and only if at least one number in the subarray is even. The solution tracks the position of the most recent even number encountered (last). For each position i, the number of subarrays ending at position i that have an even product equals last + 1 (since any subarray that includes the even number at position last will have an even product).

Intuition

To understand this problem, let's first think about when a product becomes even. A product is even when at least one of its factors is even. This means for any subarray to have an even product, it just needs to contain at least one even number.

Now, let's think about counting subarrays ending at each position. For any position i, we want to know: how many subarrays ending at position i have an even product?

The key observation is that if we know where the most recent even number is located (let's call this position last), then any subarray that:

• Ends at position i
• Starts at or after position last

will definitely have an even product because it includes that even number at position last.

For example, if we have nums = [1, 3, 2, 5] and we're at position i = 3 (value 5):

• The most recent even number is at position last = 2 (value 2)
• Subarrays ending at position 3 that have even products are:
  • [2, 5] starting from position 2
  • [3, 2, 5] starting from position 1
  • [1, 3, 2, 5] starting from position 0
• That's exactly last + 1 = 2 + 1 = 3 subarrays

This pattern holds because we can start our subarray from any position between 0 and last (inclusive), and as long as we end at the current position i, we'll include that even number at position last, making the product even.

If we haven't encountered any even number yet (last = -1), then no subarray ending at the current position can have an even product, which aligns with our formula: last + 1 = -1 + 1 = 0.

Learn more about Math and Dynamic Programming patterns.

Solution Approach

The solution uses a single-pass algorithm with constant space complexity. We maintain two variables:

• ans: accumulates the total count of subarrays with even products
• last: tracks the index of the most recent even number encountered (initialized to -1)

Here's how the algorithm works step by step:

1. Initialize variables: Set ans = 0 to store our result and last = -1 to indicate we haven't found an even number yet.

2. Iterate through the array: For each element at index i with value v:

   • Check if current element is even: If v % 2 == 0, update last = i since we've found a new even number
   • Count subarrays: Add last + 1 to our answer. This represents the number of subarrays ending at position i that have an even product

3. Return the result: After processing all elements, ans contains the total count.

Let's trace through an example with nums = [1, 2, 3, 4]:

• i = 0, v = 1 (odd): last remains -1, add (-1) + 1 = 0 to ans. Total: 0
• i = 1, v = 2 (even): Update last = 1, add 1 + 1 = 2 to ans. Total: 2
• i = 2, v = 3 (odd): last remains 1, add 1 + 1 = 2 to ans. Total: 4
• i = 3, v = 4 (even): Update last = 3, add 3 + 1 = 4 to ans. Total: 8

The formula last + 1 works because:

• If last = -1 (no even number seen yet), we add 0 (no valid subarrays)
• If last >= 0, we can form last + 1 subarrays by starting from positions 0, 1, ..., last and ending at the current position i

This approach efficiently counts all subarrays with even products in O(n) time and O(1) space.

Example Walkthrough

Let's walk through a concrete example with nums = [3, 1, 2, 5] to illustrate how the solution works.

Initial Setup:

• ans = 0 (total count of subarrays with even products)
• last = -1 (no even number seen yet)

Step 1: Process index 0, value = 3 (odd)

• 3 is odd, so last stays -1
• Subarrays ending at index 0: [3]
• None have even products (no even numbers included)
• Add last + 1 = -1 + 1 = 0 to ans
• Running total: ans = 0

Step 2: Process index 1, value = 1 (odd)

• 1 is odd, so last stays -1
• Subarrays ending at index 1: [1], [3,1]
• None have even products (still no even numbers)
• Add last + 1 = -1 + 1 = 0 to ans
• Running total: ans = 0

Step 3: Process index 2, value = 2 (even)

• 2 is even, so update last = 2
• Subarrays ending at index 2: [2], [1,2], [3,1,2]
• All three include the even number at index 2, so all have even products
• Add last + 1 = 2 + 1 = 3 to ans
• Running total: ans = 3

Step 4: Process index 3, value = 5 (odd)

• 5 is odd, so last stays 2
• Subarrays ending at index 3: [5], [2,5], [1,2,5], [3,1,2,5]
• The last three include the even number at index 2, so they have even products
• Add last + 1 = 2 + 1 = 3 to ans
• Running total: ans = 6

Final Result: 6 subarrays with even products

The key insight demonstrated here is that once we encounter an even number at position last, any subarray that includes this position will have an even product. For each new position, we can form exactly last + 1 such subarrays by choosing different starting positions (from 0 to last).

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. The algorithm iterates through the array exactly once using a single for loop with enumerate(nums). Each operation inside the loop (checking if a number is even with modulo operation, updating the last variable, and adding to ans) takes constant time O(1).

The space complexity is O(1). The algorithm only uses a fixed amount of extra space regardless of the input size. It maintains just two variables: ans to store the result and last to track the index of the most recent even number. These variables require constant space that doesn't grow with the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Confusing the Problem with Counting Odd Products

A common mistake is trying to count odd products and then subtract from the total number of subarrays. While this approach can work, it adds unnecessary complexity and is more error-prone.

Incorrect approach:

def evenProduct(self, nums: List[int]) -> int:
    n = len(nums)
    total_subarrays = n * (n + 1) // 2
    odd_count = 0
    consecutive_odds = 0
  
    for num in nums:
        if num % 2 == 1:
            consecutive_odds += 1
            odd_count += consecutive_odds
        else:
            consecutive_odds = 0
  
    return total_subarrays - odd_count  # This logic is flawed

Why it fails: The logic for counting odd product subarrays is more complex than it appears. You need to track consecutive odd segments properly, which is harder to implement correctly.

2. Off-by-One Error in Index Calculation

Developers might forget to add 1 to last_even_index when counting subarrays, or might initialize last_even_index to 0 instead of -1.

Incorrect initialization:

def evenProduct(self, nums: List[int]) -> int:
    total_count = 0
    last_even_index = 0  # Wrong! Should be -1
  
    for current_index, value in enumerate(nums):
        if value % 2 == 0:
            last_even_index = current_index
        total_count += last_even_index  # Wrong! Should be last_even_index + 1
  
    return total_count

Why it fails: Starting with last_even_index = 0 incorrectly assumes there's an even number at index 0, leading to overcounting when the array starts with odd numbers.

3. Integer Overflow in Other Languages

While Python handles large integers automatically, in languages like Java or C++, the result might overflow for large arrays.

Solution for other languages:

// Use long instead of int in Java
public long evenProduct(int[] nums) {
    long totalCount = 0;  // Use long to prevent overflow
    int lastEvenIndex = -1;
  
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] % 2 == 0) {
            lastEvenIndex = i;
        }
        totalCount += lastEvenIndex + 1;
    }
  
    return totalCount;
}

4. Misunderstanding Zero Values

If the array contains zeros, some might incorrectly handle them separately, not realizing that zero is even (0 % 2 == 0).

Incorrect special handling:

def evenProduct(self, nums: List[int]) -> int:
    total_count = 0
    last_even_index = -1
  
    for current_index, value in enumerate(nums):
        if value == 0:  # Unnecessary special case
            # Some incorrect special handling
            continue
        elif value % 2 == 0:
            last_even_index = current_index
        total_count += last_even_index + 1
  
    return total_count

Why it fails: Zero is even and should be treated like any other even number. Special handling breaks the algorithm's logic.

5. Using Two Pointers or Nested Loops

Some might overcomplicate the solution with a brute force approach that checks every subarray explicitly.

Inefficient approach:

def evenProduct(self, nums: List[int]) -> int:
    count = 0
    n = len(nums)
  
    for i in range(n):
        has_even = False
        for j in range(i, n):
            if nums[j] % 2 == 0:
                has_even = True
            if has_even:
                count += 1
  
    return count

Why it's problematic: This O(n²) solution is correct but inefficient. For large arrays, it will cause time limit exceeded errors.

Best Practice: Stick to the elegant O(n) solution that tracks the last even index. It's simpler, more efficient, and less prone to errors.