Given a sequence of n numbers. The task is to count all the subsets of the given set which only have even numbers and all are distinct.
Note: By the property of sets, if two subsets have the same set of elements then they are considered as one. For example: [2, 4, 8] and [4, 2, 8] are considered to be the same.
Examples:
Input : {4, 2, 1, 9, 2, 6, 5, 3}
Output : 7
The subsets are:
[4], [2], [6], [4, 2],
[2, 6], [4, 6], [4, 2, 6]
Input : {10, 3, 4, 2, 4, 20, 10, 6, 8, 14, 2, 6, 9}
Output : 127
A simple approach is to consider all the subsets and check whether they satisfy the given conditions or not. The time complexity will be in exponential.
An efficient approach is to count number of distinct even numbers. Let this be ceven. And then apply formula:
2ceven – 1
This is similar to counting the number of subsets of a given set of n elements. 1 is subtracted because the null set is not considered.
Implementation:
C++
// C++ implementation to count subsets having// even numbers only and all are distinct#include <bits/stdc++.h>using namespace std;// function to count the// required subsetsint countSubsets(int arr[], int n){ unordered_set<int> us; int even_count = 0; // inserting even numbers in the set 'us' // single copy of each number is retained for (int i=0; i<n; i++) if (arr[i] % 2 == 0) us.insert(arr[i]); unordered_set<int>:: iterator itr; // distinct even numbers even_count = us.size(); // total count of required subsets return (pow(2, even_count) - 1);}// Driver program to test aboveint main(){ int arr[] = {4, 2, 1, 9, 2, 6, 5, 3}; int n = sizeof(arr) / sizeof(arr[0]); cout << "Number of subsets = " << countSubsets(arr, n); return 0; } |
Java
// Java implementation to count subsets having// even numbers only and all are distinctimport java.util.*;class GFG {// function to count the// required subsetsstatic int countSubsets(int arr[], int n){ HashSet<Integer> us = new HashSet<>(); int even_count = 0; // inserting even numbers in the set 'us' // single copy of each number is retained for (int i = 0; i < n; i++) if (arr[i] % 2 == 0) us.add(arr[i]); // counting distinct even numbers even_count=us.size(); // total count of required subsets return (int) (Math.pow(2, even_count) - 1);}// Driver codepublic static void main(String[] args) { int arr[] = {4, 2, 1, 9, 2, 6, 5, 3}; int n = arr.length; System.out.println("Number of subsets = " + countSubsets(arr, n));}}// This code contributed by Rajput-Ji |
Python3
# python implementation to count subsets having # even numbers only and all are distinct #function to count the required subsets def countSubSets(arr, n): us = set() even_count = 0 # inserting even numbers in the set 'us' # single copy of each number is retained for i in range(n): if arr[i] % 2 == 0: us.add(arr[i]) # counting distinct even numbers even_count = len(us) # total count of required subsets return pow(2, even_count)- 1# Driver programarr = [4, 2, 1, 9, 2, 6, 5, 3]n = len(arr)print("Numbers of subset=", countSubSets(arr,n))# This code is contributed by Shrikant13 |
C#
// C# implementation to count subsets having// even numbers only and all are distinct using System;using System.Collections.Generic;class GFG {// function to count the// required subsetsstatic int countSubsets(int []arr, int n){ HashSet<int> us = new HashSet<int>(); int even_count = 0; // inserting even numbers in the set 'us' // single copy of each number is retained for (int i = 0; i < n; i++) if (arr[i] % 2 == 0) us.Add(arr[i]); // counting distinct even numbers even_count = us.Count; // total count of required subsets return (int) (Math.Pow(2, even_count) - 1);}// Driver codepublic static void Main(String[] args) { int[] arr = {4, 2, 1, 9, 2, 6, 5, 3}; int n = arr.Length; Console.WriteLine("Number of subsets = " + countSubsets(arr, n));}}// This code contributed by Rajput-Ji |
Javascript
<script>// Javascript implementation to count// subsets having even numbers only // and all are distinct// Function to count the// required subsetsfunction countSubsets(arr, n){ let us = new Set(); let even_count = 0; // Inserting even numbers in the set 'us' // single copy of each number is retained for(let i = 0; i < n; i++) if (arr[i] % 2 == 0) us.add(arr[i]); // Counting distinct even numbers even_count = us.size; // Total count of required subsets return Math.floor(Math.pow(2, even_count) - 1);}// Driver codelet arr = [ 4, 2, 1, 9, 2, 6, 5, 3 ];let n = arr.length;document.write("Number of subsets = " + countSubsets(arr, n));// This code is contributed by _saurabh_jaiswal</script> |
Number of subsets = 7
Time Complexity: O(n)
Auxiliary Space: O(n)
This article is contributed by Aarti_Rathi and Ayush Jauhari. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
