We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Subarrays Having Even Product

Number: 2638

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

Given an integer array nums, count and return the number of subarrays such that the product of all elements in the subarray is even. A subarray is a contiguous segment of the array. The product is even if at least one element in the subarray is even.

Key Insights

  • A product is even if and only if at least one even number is present.
  • Count total subarrays using the formula n*(n+1)/2.
  • Count subarrays with all odd numbers (none of which contribute an even factor) by grouping contiguous odd segments and summing L*(L+1)/2 for each.
  • Result equals total subarrays minus the count of all-odd subarrays.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

We solve the problem by first calculating the total number of subarrays by using the formula n*(n+1)/2 for an array of length n. Next, we iterate over the array to count all contiguous segments that consist only of odd numbers. For each segment, we calculate the number of subarrays contained in that segment using L*(L+1)/2 where L is the length of the segment. Since these subarrays never include an even number, their product is odd. Finally, subtract this count from the total subarrays to get the desired number of subarrays with an even product. The algorithm leverages simple iteration, arithmetic, and minimal extra space.

Code Solutions

# Python solution

def evenProductSubarrays(nums):
    # Calculate total subarrays using n*(n+1)/2 formula
    n = len(nums)
    total_subarrays = n * (n + 1) // 2
    
    # Count subarrays with all odd numbers
    odd_subarrays = 0
    current_odd_length = 0
    for num in nums:
        # If the number is odd, increase the current odd sequence length
        if num % 2 == 1:
            current_odd_length += 1
        else:
            # When an even number is encountered, count the subarrays formed in the current odd segment
            odd_subarrays += current_odd_length * (current_odd_length + 1) // 2
            current_odd_length = 0
    # Make sure to count any trailing odd segment after the loop
    odd_subarrays += current_odd_length * (current_odd_length + 1) // 2
    
    # The number of subarrays with an even product equals total subarrays minus all-odd subarrays
    return total_subarrays - odd_subarrays

# Example usage:
nums = [9, 6, 7, 13]
print(evenProductSubarrays(nums))  # Expected output: 6
← Back to All Questions