Question

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

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

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;
  }
}

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;
  }
};

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)
}