2495. Number of Subarrays Having Even Product

MediumArrayMathDynamic Programming
Leetcode Link

Problem Description

We are tasked with finding the number of subarrays from a given array nums, where the subarrays have a product that is an even number. A subarray is defined as a contiguous part of the original array. Since the array is 0-indexed, the first element is at position 0. Remember, a single element is also considered a subarray, so if any element in the array is even, that alone counts as one subarray with an even product. The final output should be the total count of such subarrays.

Intuition

To solve this problem, we can use the fact that the product of integers is even if and only if at least one of the integers is even. With this in mind, we scan the array and keep track of the last position last where we encountered an even number. When we find an even number, we know that all subarrays that end at that position and start before or at the last found even number's position will have an even product.

For every element v at index i, if v is odd, the number of subarrays ending at i with an even product is the same as the number of subarrays ending at i-1. If v is even, then all subarrays ending at i have an even product. We add 1 to account for the current element, which is a subarray itself if it's even. We keep on adding this quantity to a cumulative answer variable ans.

This approach avoids the need to check the product of each subarray individually, which would not be efficient for large arrays, and instead uses the properties of even/odd numbers to count the subarrays in a linear pass through the array.

Learn more about Math and Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Solution Approach

The solution is implemented in Python using a single pass through the array. The algorithm can be broken down into the following steps:

  1. Initialize two variables, ans and last. ans will hold the final result — the number of subarrays with an even product. last will store the index of the most recently found even number in the array. Initially, last is set to -1 to indicate that we haven't encountered any even numbers yet.

  2. Iterate through nums using a loop, where i is the current index, and v is the value of the current element:

    • Inside the loop, check if the current element v is even (using v % 2 == 0). If it is,
      • Update last to the current index i because we now have a new last index where the subarray with an even product can start.
    • Regardless of whether the current element is even or odd, update ans by adding last + 1 to it. The last + 1 represents the number of subarrays ending at i that include an even number and thus have an even product. This works because:
      • If v is even, all subarrays ending at i will have an even product. The number of such subarrays is i + 1 (since arrays are 0-indexed).
      • If v is odd, the subarrays that have an even product are those which start before or at the last even number found. That's why we increment ans by last + 1 instead of i + 1.

  3. Return the value of ans once the loop is completed.

The algorithm relies on simple arithmetic and control structures and does not use any specific data structure or complex pattern. It merely exploits the mathematical properties of multiplication (an even number times any other number is always even) to count the subarrays efficiently.

This approach does not explicitly construct each subarray; instead, it calculates the number of valid subarrays ending at a certain point based on knowledge of earlier components of the array. This is why the algorithm runs in O(n) time, where n is the length of the input array, because it processes each element of the array only once.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the relationship between a tree and a graph?

Example Walkthrough

Let's illustrate the solution approach using a small example. Consider the following input array:

1nums = [3, 2, 5, 6, 7]

Here is a step-by-step explanation of how we would apply the algorithm:

  1. We start by initializing ans to 0 and last to -1 because we haven't encountered any even numbers yet.

  2. We begin iterating through nums:

    • Index 0: The value 3 is odd. We do not update last, but we still update ans. Since last is -1, ans += (last + 1) results in ans = 0, indicating no subarrays ending here have an even product.

    • Index 1: The value 2 is even, so we update last to the current index (last = 1). For updating ans, we add last + 1 to it, resulting in ans += (1 + 1) which gives us ans = 2. This accounts for two subarrays [2] and [3, 2].

    • Index 2: The value 5 is odd, so last remains at 1. We update ans by adding last + 1 to it, resulting in ans += (1 + 1) which gives us ans = 4. The subarrays [2, 5] and [3, 2, 5] are the new subarrays added to the count.

    • Index 3: The value 6 is even, so we update last to the current index (last = 3). We now add last + 1 to ans, resulting in ans += (3 + 1) which gives us ans = 8. The new subarrays considered here are [6], [5, 6], [2, 5, 6], and [3, 2, 5, 6].

    • Index 4: The value 7 is odd, so last does not change and remains at 3. We update ans once again by adding last + 1 to it, resulting in ans += (3 + 1) which brings us to ans = 12. The new subarrays considered are the extensions of previous subarrays ending with 7.

  3. Once the loop is completed, we have our final answer. The value of ans is 12, so there are 12 subarrays with an even product within the array [3, 2, 5, 6, 7].

In this example, each step either adds a new set of subarrays ending with an even number or extends the existing subarrays with an odd number, while keeping track of the total count with the ans variable. This linear algorithm is efficient and takes into account the characteristics of even and odd products to dynamically calculate the total amount without the need to enumerate each possible subarray explicitly.

Solution Implementation

1from typing import List
2
3class Solution:
4    def evenProduct(self, nums: List[int]) -> int:
5        # Initialize sum_even_products to accumulate the sum of the counts
6        # and last_even_index to keep track of the last seen even number index
7        sum_even_products, last_even_index = 0, -1
8      
9        # Iterate over the list of numbers with index and value
10        for index, value in enumerate(nums):
11            # Check if the current value is even
12            if value % 2 == 0:
13                # Update the last_even_index with the current index
14                last_even_index = index
15            # Add to the sum_even_products the count of subarrays ending with an even product
16            # This is found by adding 1 to the last_even_index because if last_even_index is -1,
17            # it means no even number has been found yet, so we add 0 (-1 + 1) to the sum.
18            sum_even_products += last_even_index + 1
19      
20        # Return the accumulated sum of counts of subarrays with an even product
21        return sum_even_products
22
1class Solution {
2    public long evenProduct(int[] numbers) {
3        long answer = 0; // Initialize the answer as 0 which will hold the final result
4        int lastEvenIndex = -1; // Initialize the last even index to -1 indicating no even number encountered yet
5
6        // Iterate over the array
7        for (int i = 0; i < numbers.length; ++i) {
8            // Check if the current element is even
9            if (numbers[i] % 2 == 0) {
10                lastEvenIndex = i; // Update the index of the last seen even number
11            }
12            // Add the index of the last seen even number plus one to the answer
13            // (if no even number has been encountered, this adds 0)
14            answer += lastEvenIndex + 1;
15        }
16      
17        return answer; // Return the computed sum
18    }
19}
20
1#include <vector>
2
3class Solution {
4public:
5    // Function to calculate the sum of indices (plus one) of all even numbers encountered so far in the array.
6    long long evenProduct(std::vector<int>& nums) {
7        long long total = 0; // Initialize the sum as a long long to handle large numbers.
8        int lastIndex = -1; // Keep track of the last encountered even number's index. Start with -1 since we haven't encountered any even numbers yet.
9
10        // Loop through each number in the vector.
11        for (int i = 0; i < nums.size(); ++i) {
12            // Check if the current number is even.
13            if (nums[i] % 2 == 0) {
14                // Update the lastIndex with the current index i if the number is even.
15                lastIndex = i;
16            }
17            // Add one to the lastIndex since we need to accumulate indices starting from 1.
18            // When lastIndex is -1, it implies that no even numbers have been found up to the current index,
19            // so it adds 0 (lastIndex + 1) to the total.
20            total += lastIndex + 1;
21        }
22        // Return the accumulated sum.
23        return total;
24    }
25};
26
1// A function to calculate the sum of indices (plus one) of all even numbers encountered so far in the array.
2function evenProduct(nums: number[]): number {
3    let total: number = 0; // Initialize the sum to handle large numbers.
4    let lastEvenIndex: number = -1; // Keep track of the last encountered even number's index. Start with -1 since we haven't encountered any even numbers yet.
5
6    // Loop through each number in the array.
7    for (let i = 0; i < nums.length; i++) {
8        // Check if the current number is even.
9        if (nums[i] % 2 === 0) {
10            // Update the lastEvenIndex with the current index i if the number is even.
11            lastEvenIndex = i;
12        }
13        // Add one to the lastEvenIndex. If lastEvenIndex is -1, this adds 0 to the total.
14        total += lastEvenIndex + 1;
15    }
16    // Return the accumulated sum.
17    return total;
18}
19
20// Example usage:
21// let arr = [1, 2, 3, 4];
22// let sum = evenProduct(arr);
23// console.log(sum); // Output will depend on the array provided
24
Not Sure What to Study? Take the 2-min Quiz

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Time and Space Complexity

The given Python code defines a method evenProduct that calculates the sum of the indices of the last even number seen in a list of integers up to each element in the list.

Time Complexity

The time complexity of the code is O(n), where n is the length of the input list nums. This is because the code contains a single loop that iterates through the list nums. During each iteration, the code performs a constant-time check to determine whether an element is even (i.e., v % 2 == 0), and it updates two variables, last and ans, with simple arithmetic operations, which also take constant time.

Space Complexity

The space complexity of the code is O(1) because the extra space used by the algorithm is constant and does not depend on the size of the input list. The variables ans and last are used for storing the running total and the index of the last encountered even number, respectively, and their space usage does not scale with the input size.

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

Fast Track Your Learning with Our Quick Skills Quiz:

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA đŸ‘šâ€đŸ«