Problem

Given a 0-indexed integer array nums, return _the number of subarrays of _nums having an even product.

Examples

Example 1:

1
2
3
4
5
6
7
8
9

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:

1
2
3

Input: nums = [7,3,5]
Output: 0
Explanation: There are no subarrays with an even product.

Constraints:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5

Solution

Method 1 – Counting Odd Prefixes

Intuition

The product of a subarray is even if and only if at least one element in the subarray is even. So, for each subarray, if it contains an even number, its product is even. Instead of checking every subarray, we can count the number of subarrays that are all odd (whose product is odd), and subtract this from the total number of subarrays to get the answer.

Approach

  1. Let n be the length of nums.
  2. The total number of subarrays is n * (n + 1) / 2.
  3. Count the number of subarrays that contain only odd numbers:
    • Iterate through nums, for each maximal contiguous segment of odd numbers, say of length len, it contributes len * (len + 1) / 2 all-odd subarrays.
  4. Subtract the count of all-odd subarrays from the total to get the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    long long evenProduct(vector<int>& nums) {
        long long n = nums.size(), ans = n * (n + 1) / 2, odd = 0, cnt = 0;
        for (int x : nums) {
            if (x % 2 == 1) {
                ++cnt;
            } else {
                odd += cnt * (cnt + 1) / 2;
                cnt = 0;
            }
        }
        odd += cnt * (cnt + 1) / 2;
        return ans - odd;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func evenProduct(nums []int) int64 {
    n := int64(len(nums))
    ans := n * (n + 1) / 2
    odd, cnt := int64(0), int64(0)
    for _, x := range nums {
        if x%2 == 1 {
            cnt++
        } else {
            odd += cnt * (cnt + 1) / 2
            cnt = 0
        }
    }
    odd += cnt * (cnt + 1) / 2
    return ans - odd
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public long evenProduct(int[] nums) {
        long n = nums.length, ans = n * (n + 1) / 2, odd = 0, cnt = 0;
        for (int x : nums) {
            if (x % 2 == 1) {
                ++cnt;
            } else {
                odd += cnt * (cnt + 1) / 2;
                cnt = 0;
            }
        }
        odd += cnt * (cnt + 1) / 2;
        return ans - odd;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    fun evenProduct(nums: IntArray): Long {
        val n = nums.size.toLong()
        var ans = n * (n + 1) / 2
        var odd = 0L
        var cnt = 0L
        for (x in nums) {
            if (x % 2 == 1) {
                cnt++
            } else {
                odd += cnt * (cnt + 1) / 2
                cnt = 0
            }
        }
        odd += cnt * (cnt + 1) / 2
        return ans - odd
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def evenProduct(self, nums: list[int]) -> int:
        n = len(nums)
        ans = n * (n + 1) // 2
        odd = cnt = 0
        for x in nums:
            if x % 2 == 1:
                cnt += 1
            else:
                odd += cnt * (cnt + 1) // 2
                cnt = 0
        odd += cnt * (cnt + 1) // 2
        return ans - odd
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn even_product(nums: Vec<i32>) -> i64 {
        let n = nums.len() as i64;
        let mut ans = n * (n + 1) / 2;
        let mut odd = 0i64;
        let mut cnt = 0i64;
        for &x in &nums {
            if x % 2 == 1 {
                cnt += 1;
            } else {
                odd += cnt * (cnt + 1) / 2;
                cnt = 0;
            }
        }
        odd += cnt * (cnt + 1) / 2;
        ans - odd
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    evenProduct(nums: number[]): number {
        const n = nums.length;
        let ans = n * (n + 1) / 2;
        let odd = 0, cnt = 0;
        for (const x of nums) {
            if (x % 2 === 1) {
                cnt++;
            } else {
                odd += cnt * (cnt + 1) / 2;
                cnt = 0;
            }
        }
        odd += cnt * (cnt + 1) / 2;
        return ans - odd;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of nums, since we scan the array once.
  • 🧺 Space complexity: O(1), as we use only a constant amount of extra space for counters.