README_EN.md

comments	difficulty	edit_url	tags
true	Medium	https://github.com/doocs/leetcode/edit/main/solution/2400-2499/2495.Number%20of%20Subarrays%20Having%20Even%20Product/README_EN.md	Array Math Dynamic Programming

2495. Number of Subarrays Having Even Product 🔒

中文文档

Description

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

Solutions

Solution 1: Single Pass

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)$.

Python3

class Solution:
    def evenProduct(self, nums: List[int]) -> int:
        ans, last = 0, -1
        for i, v in enumerate(nums):
            if v % 2 == 0:
                last = i
            ans += last + 1
        return ans

Java

class Solution {
    public long evenProduct(int[] nums) {
        long ans = 0;
        int last = -1;
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] % 2 == 0) {
                last = i;
            }
            ans += last + 1;
        }
        return ans;
    }
}

C++

class Solution {
public:
    long long evenProduct(vector<int>& nums) {
        long long ans = 0;
        int last = -1;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] % 2 == 0) {
                last = i;
            }
            ans += last + 1;
        }
        return ans;
    }
};

Go

func evenProduct(nums []int) int64 {
	ans, last := 0, -1
	for i, v := range nums {
		if v%2 == 0 {
			last = i
		}
		ans += last + 1
	}
	return int64(ans)
}