Total number of subsets in which the product of the elements is even

0 0 3 minutes read

Given an array arr[] of integer elements, the task is to find the total number of sub-sets of arr[] in which the product of the elements is even.

Examples:

Input: arr[] = {2, 2, 3}
Output: 6
All possible sub-sets are {2}, {2}, {2, 2}, {2, 3}, {2, 3} and {2, 2, 3}

Input: arr[] = {3, 3, 3}
Output: 6

Approach: We already know that:

Even * Even = Even
Odd * Even = Even
Odd * Odd = Odd

Now, we need to count the total subsets in which at least a single even element is present in order for the product of the elements to be even.
Now, Total number of sub-sets having at least one even element = Total possible sub-sets of n – Total sub-sets having all odd elements
i.e. (2ⁿ – 1) – (2^totalOdd – 1)

Below is the implementation of the above approach:

C++

// C++ implementation of above approach
 
#include <iostream>
#include<bits/stdc++.h>
 
using namespace std;
 
// Function to find total number of subsets 
// in which product of the elements is even
void find(int a[], int n)
{
    int count_odd = 0;
     
    for(int i = 0; i < n ; i++)
    {
        // counting number of odds elements
        if (i % 2 != 0)
        count_odd += 1;
    }
 
    int result = pow(2, n) - 1 ;
    result -= (pow(2, count_odd) - 1) ;
    cout << result << endl;
     
}
 
// Driver code
int main()
{
   int a[] = {2, 2, 3} ;
   int n = sizeof(a)/sizeof(a[0]) ;
    
   // function calling
   find(a,n);
    
   return 0;
   // This code is contributed by ANKITRAI1;
}

Java

// Java implementation of above approach 
 
class GFG {
 
// Function to find total number of subsets 
// in which product of the elements is even 
    static void find(int a[], int n) {
        int count_odd = 0;
 
        for (int i = 0; i < n; i++) {
            // counting number of odds elements 
            if (i % 2 != 0) {
                count_odd += 1;
            }
        }
 
        int result = (int) (Math.pow(2, n) - 1);
        result -= (Math.pow(2, count_odd) - 1);
        System.out.println(result);
 
    }
 
// Driver code 
    public static void main(String[] args) {
        int a[] = {2, 2, 3};
        int n = a.length;
 
// function calling 
        find(a, n);
 
    }
}
//this code contributed by 29AJayKumar

Python3

# Python3 implementation of above approach
import math as ma
 
# Function to find total number of subsets 
# in which product of the elements is even
def find(a):
    count_odd = 0
    for i in a:
 
        # counting number of odds elements
        if(i % 2 != 0):
            count_odd+= 1
 
    result = pow(2, len(a)) - 1
    result = result - (pow(2, count_odd) - 1)
    print(result)
 
# Driver code
a =[2, 2, 3]
find(a)

C#

     
// C# implementation of above approach 
using System;
public class GFG {
  
// Function to find total number of subsets 
// in which product of the elements is even 
    static void find(int []a, int n) {
        int count_odd = 0;
  
        for (int i = 0; i < n; i++) {
            // counting number of odds elements 
            if (i % 2 != 0) {
                count_odd += 1;
            }
        }
  
        int result = (int) (Math.Pow(2, n) - 1);
        result -= (int)(Math.Pow(2, count_odd) - 1);
        Console.Write(result);
  
    }
  
// Driver code 
    public static void Main() {
        int []a = {2, 2, 3};
        int n = a.Length;
  
// function calling 
        find(a, n);
  
    }
}
//this code contributed by 29AJayKumar

PHP

<?php 
// PHP implementation of above approach
  
// Function to find total number of subsets 
// in which product of the elements is even
function find(&$a, $n)
{
    $count_odd = 0;
      
    for($i = 0; $i < $n ; $i++)
    {
        // counting number of odds elements
        if ($i % 2 != 0)
        $count_odd += 1;
    }
  
    $result = pow(2, $n) - 1 ;
    $result -= (pow(2, $count_odd) - 1) ;
    echo $result ."\n";
      
}
  
// Driver code
 
$a = array(2, 2, 3) ;
$n = sizeof($a)/sizeof($a[0]) ;
 
// function calling
find($a,$n);
 
return 0;
 
?>

Javascript

<script>
 
// Javascript implementation of above approach
 
// Function to find total number of subsets 
// in which product of the elements is even
function find(a, n)
{
    var count_odd = 0;
     
    for(var i = 0; i < n ; i++)
    {
        // counting number of odds elements
        if (i % 2 != 0)
            count_odd += 1;
    }
 
    var result = Math.pow(2, n) - 1 ;
    result -= (Math.pow(2, count_odd) - 1) ;
    document.write( result );
     
}
 
// Driver code
var a = [2, 2, 3];
var n = a.length;
 
// function calling
find(a,n);
 
</script>

Output

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 zambiatek!