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. (2n – 1) – (2totalOdd – 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 evenvoid 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 codeint 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 approachimport math as ma# Function to find total number of subsets # in which product of the elements is evendef 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 codea =[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 evenfunction 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 callingfind($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 evenfunction 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 codevar a = [2, 2, 3];var n = a.length;// function callingfind(a,n);</script> |
Output
6
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!
