Data Modelling & AI Data Structure & Algorithm

Number of subarrays having even product

21 June 2025

0

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 product
void 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 Code
int 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 approach
import 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 product
def 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 Code
if __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 approach
using 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 product
function 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:

Time Complexity: O(N²)
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 product
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 < 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 code
int 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 approach
import 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 product
def 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 code
if __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 approach
using 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:

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!

Number of subarrays having even product

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

LangExtract + Milvus: A Practical Guide to Building a Hybrid Document Processing and Search System

Stop Your AI Assistant from Writing Outdated Code with Milvus SDK Code Helper

A Practical Guide for Choosing the Right Vector Database for Your AI Applications

LEAVE A REPLY Cancel reply

Most Popular

Why I’d skip the carrier store for this Google Store–only Pixel 10 setup perk

A big change is coming to OnePlus’s cameras

The Pixel 10 has serious pairing issues with the Samsung Galaxy Watch

Samsung Galaxy S26 Ultra could get bigger and rounder

EDITOR PICKS

Why I’d skip the carrier store for this Google Store–only Pixel 10 setup perk

A big change is coming to OnePlus’s cameras

The Pixel 10 has serious pairing issues with the Samsung Galaxy Watch

POPULAR POSTS

Why I’d skip the carrier store for this Google Store–only Pixel 10 setup perk

A big change is coming to OnePlus’s cameras

The Pixel 10 has serious pairing issues with the Samsung Galaxy Watch

POPULAR CATEGORY

ABOUT US

FOLLOW US