LeetCode 2495: Number of Subarrays Having Even Product

Explanation:

To solve this problem, we can iterate through the array and keep track of the number of subarrays with even product. We can do this by maintaining a count of the number of odd and even elements encountered so far.

For any subarray to have an even product, it must have an even number of odd elements. We can keep track of the count of odd elements encountered so far.

As we iterate through the array, we count the number of odd and even elements. For each new element, we update the count of odd and even elements. Whenever we encounter an odd element, we increment the count of odd elements and calculate the number of subarrays that can be formed with even product using the count of odd elements.

The total number of subarrays with even product will be the sum of the counts of subarrays with even product calculated for each element.

Time complexity: O(N), where N is the number of elements in the array. Space complexity: O(1)

:

class Solution {
    public int numSubarraysWithEvenProduct(int[] nums) {
        int count = 0;
        int oddCount = 0;
        int result = 0;
        
        for (int num : nums) {
            if (num % 2 == 1) {
                oddCount++;
                count = 0;
            } else {
                count++;
                result += oddCount;
            }
            result += count;
        }
        
        return result;
    }
}