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