Skip to content

2495. Number of Subarrays Having Even Product πŸ”’

DifficultyMedium

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

Thinking

A subarray product is even iff it contains an even. For right end \(i\), the left end may be any index up to the latest even, i.e. \(\textit{last}+1\) choices (\(0\) if none). One pass keeps \(\textit{last}\).

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 \(\textit{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)\), and the space complexity is \(O(1)\), where \(n\) is the length of the array \(\textit{nums}\).

1
2
3
4
5
6
7
8
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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)
}

Comments