2495. Number of Subarrays Having Even Product
Problem Description
We are tasked with finding the number of subarrays from a given array nums
, where the subarrays have a product that is an even number. A subarray is defined as a contiguous part of the original array. Since the array is 0-indexed, the first element is at position 0. Remember, a single element is also considered a subarray, so if any element in the array is even, that alone counts as one subarray with an even product. The final output should be the total count of such subarrays.
Intuition
To solve this problem, we can use the fact that the product of integers is even if and only if at least one of the integers is even. With this in mind, we scan the array and keep track of the last position last
where we encountered an even number. When we find an even number, we know that all subarrays that end at that position and start before or at the last found even number's position will have an even product.
For every element v
at index i
, if v
is odd, the number of subarrays ending at i
with an even product is the same as the number of subarrays ending at i-1
. If v
is even, then all subarrays ending at i
have an even product. We add 1 to account for the current element, which is a subarray itself if it's even. We keep on adding this quantity to a cumulative answer variable ans
.
This approach avoids the need to check the product of each subarray individually, which would not be efficient for large arrays, and instead uses the properties of even/odd numbers to count the subarrays in a linear pass through the array.
Learn more about Math and Dynamic Programming patterns.
Solution Approach
The solution is implemented in Python using a single pass through the array. The algorithm can be broken down into the following steps:
-
Initialize two variables,
ans
andlast
.ans
will hold the final result ā the number of subarrays with an even product.last
will store the index of the most recently found even number in the array. Initially,last
is set to -1 to indicate that we haven't encountered any even numbers yet. -
Iterate through
nums
using a loop, wherei
is the current index, andv
is the value of the current element:- Inside the loop, check if the current element
v
is even (usingv % 2 == 0
). If it is,- Update
last
to the current indexi
because we now have a new last index where the subarray with an even product can start.
- Update
- Regardless of whether the current element is even or odd, update
ans
by addinglast + 1
to it. Thelast + 1
represents the number of subarrays ending ati
that include an even number and thus have an even product. This works because:- If
v
is even, all subarrays ending ati
will have an even product. The number of such subarrays isi + 1
(since arrays are 0-indexed). - If
v
is odd, the subarrays that have an even product are those which start before or at the last even number found. That's why we incrementans
bylast + 1
instead ofi + 1
.
- If
- Inside the loop, check if the current element
-
Return the value of
ans
once the loop is completed.
The algorithm relies on simple arithmetic and control structures and does not use any specific data structure or complex pattern. It merely exploits the mathematical properties of multiplication (an even number times any other number is always even) to count the subarrays efficiently.
This approach does not explicitly construct each subarray; instead, it calculates the number of valid subarrays ending at a certain point based on knowledge of earlier components of the array. This is why the algorithm runs in O(n) time, where n is the length of the input array, because it processes each element of the array only once.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach using a small example. Consider the following input array:
nums = [3, 2, 5, 6, 7]
Here is a step-by-step explanation of how we would apply the algorithm:
-
We start by initializing
ans
to 0 andlast
to -1 because we haven't encountered any even numbers yet. -
We begin iterating through
nums
:-
Index 0: The value
3
is odd. We do not updatelast
, but we still updateans
. Sincelast
is -1,ans += (last + 1)
results inans = 0
, indicating no subarrays ending here have an even product. -
Index 1: The value
2
is even, so we updatelast
to the current index (last = 1
). For updatingans
, we addlast + 1
to it, resulting inans += (1 + 1)
which gives usans = 2
. This accounts for two subarrays[2]
and[3, 2]
. -
Index 2: The value
5
is odd, solast
remains at1
. We updateans
by addinglast + 1
to it, resulting inans += (1 + 1)
which gives usans = 4
. The subarrays[2, 5]
and[3, 2, 5]
are the new subarrays added to the count. -
Index 3: The value
6
is even, so we updatelast
to the current index (last = 3
). We now addlast + 1
toans
, resulting inans += (3 + 1)
which gives usans = 8
. The new subarrays considered here are[6]
,[5, 6]
,[2, 5, 6]
, and[3, 2, 5, 6]
. -
Index 4: The value
7
is odd, solast
does not change and remains at3
. We updateans
once again by addinglast + 1
to it, resulting inans += (3 + 1)
which brings us toans = 12
. The new subarrays considered are the extensions of previous subarrays ending with7
.
-
-
Once the loop is completed, we have our final answer. The value of
ans
is12
, so there are 12 subarrays with an even product within the array[3, 2, 5, 6, 7]
.
In this example, each step either adds a new set of subarrays ending with an even number or extends the existing subarrays with an odd number, while keeping track of the total count with the ans
variable. This linear algorithm is efficient and takes into account the characteristics of even and odd products to dynamically calculate the total amount without the need to enumerate each possible subarray explicitly.
Solution Implementation
1from typing import List
2
3class Solution:
4 def evenProduct(self, nums: List[int]) -> int:
5 # Initialize sum_even_products to accumulate the sum of the counts
6 # and last_even_index to keep track of the last seen even number index
7 sum_even_products, last_even_index = 0, -1
8
9 # Iterate over the list of numbers with index and value
10 for index, value in enumerate(nums):
11 # Check if the current value is even
12 if value % 2 == 0:
13 # Update the last_even_index with the current index
14 last_even_index = index
15 # Add to the sum_even_products the count of subarrays ending with an even product
16 # This is found by adding 1 to the last_even_index because if last_even_index is -1,
17 # it means no even number has been found yet, so we add 0 (-1 + 1) to the sum.
18 sum_even_products += last_even_index + 1
19
20 # Return the accumulated sum of counts of subarrays with an even product
21 return sum_even_products
22
1class Solution {
2 public long evenProduct(int[] numbers) {
3 long answer = 0; // Initialize the answer as 0 which will hold the final result
4 int lastEvenIndex = -1; // Initialize the last even index to -1 indicating no even number encountered yet
5
6 // Iterate over the array
7 for (int i = 0; i < numbers.length; ++i) {
8 // Check if the current element is even
9 if (numbers[i] % 2 == 0) {
10 lastEvenIndex = i; // Update the index of the last seen even number
11 }
12 // Add the index of the last seen even number plus one to the answer
13 // (if no even number has been encountered, this adds 0)
14 answer += lastEvenIndex + 1;
15 }
16
17 return answer; // Return the computed sum
18 }
19}
20
1#include <vector>
2
3class Solution {
4public:
5 // Function to calculate the sum of indices (plus one) of all even numbers encountered so far in the array.
6 long long evenProduct(std::vector<int>& nums) {
7 long long total = 0; // Initialize the sum as a long long to handle large numbers.
8 int lastIndex = -1; // Keep track of the last encountered even number's index. Start with -1 since we haven't encountered any even numbers yet.
9
10 // Loop through each number in the vector.
11 for (int i = 0; i < nums.size(); ++i) {
12 // Check if the current number is even.
13 if (nums[i] % 2 == 0) {
14 // Update the lastIndex with the current index i if the number is even.
15 lastIndex = i;
16 }
17 // Add one to the lastIndex since we need to accumulate indices starting from 1.
18 // When lastIndex is -1, it implies that no even numbers have been found up to the current index,
19 // so it adds 0 (lastIndex + 1) to the total.
20 total += lastIndex + 1;
21 }
22 // Return the accumulated sum.
23 return total;
24 }
25};
26
1// A function to calculate the sum of indices (plus one) of all even numbers encountered so far in the array.
2function evenProduct(nums: number[]): number {
3 let total: number = 0; // Initialize the sum to handle large numbers.
4 let lastEvenIndex: number = -1; // Keep track of the last encountered even number's index. Start with -1 since we haven't encountered any even numbers yet.
5
6 // Loop through each number in the array.
7 for (let i = 0; i < nums.length; i++) {
8 // Check if the current number is even.
9 if (nums[i] % 2 === 0) {
10 // Update the lastEvenIndex with the current index i if the number is even.
11 lastEvenIndex = i;
12 }
13 // Add one to the lastEvenIndex. If lastEvenIndex is -1, this adds 0 to the total.
14 total += lastEvenIndex + 1;
15 }
16 // Return the accumulated sum.
17 return total;
18}
19
20// Example usage:
21// let arr = [1, 2, 3, 4];
22// let sum = evenProduct(arr);
23// console.log(sum); // Output will depend on the array provided
24
Time and Space Complexity
The given Python code defines a method evenProduct
that calculates the sum of the indices of the last even number seen in a list of integers up to each element in the list.
Time Complexity
The time complexity of the code is O(n)
, where n
is the length of the input list nums
. This is because the code contains a single loop that iterates through the list nums
. During each iteration, the code performs a constant-time check to determine whether an element is even (i.e., v % 2 == 0
), and it updates two variables, last
and ans
, with simple arithmetic operations, which also take constant time.
Space Complexity
The space complexity of the code is O(1)
because the extra space used by the algorithm is constant and does not depend on the size of the input list. The variables ans
and last
are used for storing the running total and the index of the last encountered even number, respectively, and their space usage does not scale with the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the output of running the following function using input [30, 20, 10, 100, 33, 12]
?
1def fun(arr: List[int]) -> List[int]:
2 import heapq
3 heapq.heapify(arr)
4 res = []
5 for i in range(3):
6 res.append(heapq.heappop(arr))
7 return res
8
1public static int[] fun(int[] arr) {
2 int[] res = new int[3];
3 PriorityQueue<Integer> heap = new PriorityQueue<>();
4 for (int i = 0; i < arr.length; i++) {
5 heap.add(arr[i]);
6 }
7 for (int i = 0; i < 3; i++) {
8 res[i] = heap.poll();
9 }
10 return res;
11}
12
1class HeapItem {
2 constructor(item, priority = item) {
3 this.item = item;
4 this.priority = priority;
5 }
6}
7
8class MinHeap {
9 constructor() {
10 this.heap = [];
11 }
12
13 push(node) {
14 // insert the new node at the end of the heap array
15 this.heap.push(node);
16 // find the correct position for the new node
17 this.bubble_up();
18 }
19
20 bubble_up() {
21 let index = this.heap.length - 1;
22
23 while (index > 0) {
24 const element = this.heap[index];
25 const parentIndex = Math.floor((index - 1) / 2);
26 const parent = this.heap[parentIndex];
27
28 if (parent.priority <= element.priority) break;
29 // if the parent is bigger than the child then swap the parent and child
30 this.heap[index] = parent;
31 this.heap[parentIndex] = element;
32 index = parentIndex;
33 }
34 }
35
36 pop() {
37 const min = this.heap[0];
38 this.heap[0] = this.heap[this.size() - 1];
39 this.heap.pop();
40 this.bubble_down();
41 return min;
42 }
43
44 bubble_down() {
45 let index = 0;
46 let min = index;
47 const n = this.heap.length;
48
49 while (index < n) {
50 const left = 2 * index + 1;
51 const right = left + 1;
52
53 if (left < n && this.heap[left].priority < this.heap[min].priority) {
54 min = left;
55 }
56 if (right < n && this.heap[right].priority < this.heap[min].priority) {
57 min = right;
58 }
59 if (min === index) break;
60 [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61 index = min;
62 }
63 }
64
65 peek() {
66 return this.heap[0];
67 }
68
69 size() {
70 return this.heap.length;
71 }
72}
73
74function fun(arr) {
75 const heap = new MinHeap();
76 for (const x of arr) {
77 heap.push(new HeapItem(x));
78 }
79 const res = [];
80 for (let i = 0; i < 3; i++) {
81 res.push(heap.pop().item);
82 }
83 return res;
84}
85
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!