Given an array arr[] consisting of N integers, the task is to count the total number of subarrays having even product.
Examples :
Input: arr[] = { 7, 5, 4, 9 }
Output: 6
Explanation: There are total 6 subarrays
- { 4 }
- { 5, 4 }
- { 7, 5, 4 }
- { 7, 5, 4, 9 }
- { 5, 4, 9 }
- { 4, 9 }
Input: arr[] = { 1, 3, 5 }
Output: 0
Naive Approach: The simplest approach to solve this problem is to generate all possible subarrays from the given array and for each subarray, check if its product is even or not. If found to be true for any subarray, increase count. Finally, print the count obtained.
Below is the implementation of the above approach:
C++
// CPP implementation of the above approach#include<bits/stdc++.h>using namespace std;// Function to count subarrays with even productvoid evenproduct(int arr[], int length){ // Stores count of subarrays // with even product int count = 0; // Traverse the array for (int i = 0; i < length+1; i++) { // Initialize product int product = 1; for (int j = i; j < length+1; j++) { // Update product of the subarray product *= arr[j]; if (product % 2 == 0) ++count; } } // Print total count of subarrays cout<<count;}// Driver Codeint main(){ // Input int arr[] = { 7, 5, 4, 9 }; // Length of an array int length = (sizeof(arr)/sizeof(arr[0]))- 1; // Function call to count // subarrays with even product evenproduct(arr, length);}// This code is contributed by ipg2016107 |
Java
// Java implementation of the above approachimport java.io.*;class GFG { // Function to count subarrays with even product static void evenproduct(int arr[], int length) { // Stores count of subarrays // with even product int count = 0; // Traverse the array for (int i = 0; i < arr.length; i++) { // Initialize product int product = 1; for (int j = i; j < arr.length; j++) { // Update product of the subarray product *= arr[j]; if (product % 2 == 0) ++count; } } // Print total count of subarrays System.out.println(count); } // Driver Code public static void main(String[] args) { // Input int arr[] = { 7, 5, 4, 9 }; // Length of an array int length = arr.length - 1; // Function call to count // subarrays with even product evenproduct(arr, length); }} |
Python3
# Python3 implementation of the above approach# Function to count subarrays with even productdef evenproduct(arr, length) : # Stores count of subarrays # with even product count = 0; # Traverse the array for i in range(length + 1) : # Initialize product product = 1; for j in range(i, length + 1) : # Update product of the subarray product *= arr[j]; if (product % 2 == 0) : count += 1; # Print total count of subarrays print(count);# Driver Codeif __name__ == "__main__" : # Input arr = [ 7, 5, 4, 9 ]; # Length of an array length = len(arr) - 1; # Function call to count # subarrays with even product evenproduct(arr, length); # This code is contributed by AnkThon |
C#
// C# implementation of the above approachusing System;public class GFG { // Function to count subarrays with even product static void evenproduct(int []arr, int length) { // Stores count of subarrays // with even product int count = 0; // Traverse the array for (int i = 0; i < arr.Length; i++) { // Initialize product int product = 1; for (int j = i; j < arr.Length; j++) { // Update product of the subarray product *= arr[j]; if (product % 2 == 0) ++count; } } // Print total count of subarrays Console.WriteLine(count); } // Driver Code public static void Main(string[] args) { // Input int []arr = { 7, 5, 4, 9 }; // Length of an array int length = arr.Length - 1; // Function call to count // subarrays with even product evenproduct(arr, length); }}// This code is contributed by AnkThon |
Javascript
<script>// Javascript implementation of the above approach// Function to count subarrays with even productfunction evenproduct(arr, length){ // Stores count of subarrays // with even product var count = 0; var i,j; // Traverse the array for (i = 0; i < length+1; i++) { // Initialize product var product = 1; for (j = i; j < length+1; j++) { // Update product of the subarray product *= arr[j]; if (product % 2 == 0) ++count; } } // Print total count of subarrays document.write(count);}// Driver Code // Input var arr = [7, 5, 4, 9]; // Length of an array var length = arr.length; // Function call to count // subarrays with even product evenproduct(arr, length);</script> |
Output:
6
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: Follow the steps below to optimize the above approach:
- The total number of subarrays in an array of size N is N * (N + 1) / 2.
- The count of subarrays with an odd product is equal to the total number of continuous odd elements present in the array.
- Therefore, count of subarrays with even product = (Total number of subarrays – Subarrays with the odd product).
- Print the obtained value of the count of subarrays.
Below is the implementation of the above approach:
C++
#include <iostream>using namespace std;// Function to count subarrays// with even productvoid evenproduct(int arr[], int length){ // Total number of subarrays int total_subarray = length * (length + 1) / 2; // Counter variables int total_odd = 0; int count_odd = 0; // Traverse the array for (int i = 0; i < length; ++i) { // If current element is odd if (arr[i] % 2 == 0) { count_odd = 0; } else { ++count_odd; // Update count of subarrays // with odd product up to index i total_odd += count_odd; } } // Print count of subarrays // with even product cout << (total_subarray - total_odd) << endl;}// Driver codeint main() { // Input int arr[] = { 7, 5, 4, 9 }; // Length of an array int length = sizeof(arr) / sizeof(arr[0]); // Function call to count // even product subarrays evenproduct(arr, length); return 0;}// This code is contributed by splevel62. |
Java
// Java implementation of the above approachimport java.io.*;class GFG { // Function to count subarrays // with even product static void evenproduct(int arr[], int length) { // Total number of subarrays int total_subarray = length * (length + 1) / 2; // Counter variables int total_odd = 0; int count_odd = 0; // Traverse the array for (int i = 0; i < arr.length; ++i) { // If current element is odd if (arr[i] % 2 == 0) { count_odd = 0; } else { ++count_odd; // Update count of subarrays // with odd product up to index i total_odd += count_odd; } } // Print count of subarrays // with even product System.out.println(total_subarray - total_odd); } // Driver Code public static void main(String[] args) { // Input int arr[] = { 7, 5, 4, 9 }; // Length of an array int length = arr.length; // Function call to count // even product subarrays evenproduct(arr, length); }} |
Python3
# Function to count subarrays# with even productdef evenproduct(arr, length): # Total number of subarrays total_subarray = length * (length + 1) // 2 # Counter variables total_odd = 0 count_odd = 0 # Traverse the array for i in range(length): # If current element is odd if (arr[i] % 2 == 0): count_odd = 0 else: count_odd += 1 # Update count of subarrays # with odd product up to index i total_odd += count_odd # Print count of subarrays # with even product print(total_subarray - total_odd)# Driver codeif __name__ == "__main__": # Input arr = [7, 5, 4, 9] # Length of an array length = len(arr) # Function call to count # even product subarrays evenproduct(arr, length) # This code is contributed by ukasp. |
C#
// C# program for the above approachusing System;class GFG{ // Function to count subarrays // with even product static void evenproduct(int[] arr, int length) { // Total number of subarrays int total_subarray = length * (length + 1) / 2; // Counter variables int total_odd = 0; int count_odd = 0; // Traverse the array for (int i = 0; i < arr.Length; ++i) { // If current element is odd if (arr[i] % 2 == 0) { count_odd = 0; } else { ++count_odd; // Update count of subarrays // with odd product up to index i total_odd += count_odd; } } // Print count of subarrays // with even product Console.WriteLine(total_subarray - total_odd); } // Driver Code public static void Main(string[] args) { // Input int[] arr = { 7, 5, 4, 9 }; // Length of an array int length = arr.Length; // Function call to count // even product subarrays evenproduct(arr, length); }}// This code is contributed by code_hunt. |
Javascript
<script>// javascript implementation of the above approach // Function to count subarrays // with even product function evenproduct(arr, length) { // Total number of subarrays var total_subarray = length * (length + 1) / 2; // Counter variables var total_odd = 0; var count_odd = 0; // Traverse the array for (i = 0; i < arr.length; ++i) { // If current element is odd if (arr[i] % 2 == 0) { count_odd = 0; } else { ++count_odd; // Update count of subarrays // with odd product up to index i total_odd += count_odd; } } // Print count of subarrays // with even product document.write(total_subarray - total_odd); } // Driver Code // Input var arr = [ 7, 5, 4, 9 ]; // Length of an array var length = arr.length; // Function call to count // even product subarrays evenproduct(arr, length);// This code is contributed by Amit Katiyar </script> |
Output:
6
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
