Number of Subarrays Having Even Product — LeetCode 2495 Python Solution
MediumLeetCode PremiumArrayMathDynamic Programming
- Problem
- #2495
- Pattern
- Dynamic Programming
- Reading time
- 2 min
- Source
- leetcode.com
The problem
Given a 0-indexed integer array nums, return the number of subarrays of nums having an even product.
Example
- Input
- nums = [9,6,7,13]
- Output
- 6
- Explanation
- There are 6 subarrays with an even product:
Python solution
Python
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 ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(n), where n is the length of the array `nums` |
| Space | O(1) auxiliary |
Pattern: Dynamic Programming
Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 2495. Number of Subarrays Having Even Product is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.
The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 2495. Number of Subarrays Having Even Product?
- LeetCode 2495. Number of Subarrays Having Even Product is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2495. Number of Subarrays Having Even Product?
- The Python solution on this page runs in O(n), where n is the length of the array `nums`.
- What is the space complexity of LeetCode 2495. Number of Subarrays Having Even Product?
- The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 2495. Number of Subarrays Having Even Product cover?
- LeetCode 2495. Number of Subarrays Having Even Product is tagged Array, Math and Dynamic Programming on LeetCode.
- Is LeetCode 2495. Number of Subarrays Having Even Product a premium problem?
- Yes. LeetCode 2495. Number of Subarrays Having Even Product is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.