Count of Subsets of a given Set with element X present in it
Given an array arr[] of N unique positive integers and an element X, the task is to count the total possible number of subsets of the given set in which element X is present.
Examples:
Input: arr[] = [4, 5, 6, 7], X = 5
Output: 8
Explanation:
All subsets in which element 5 is present are:
{5}, {4, 5}, {5, 6}, {5, 7}, {4, 5, 6}, {4, 5, 7}, {5, 6, 7}, {4, 5, 6, 7}Input: arr[] = [1, 2, 3], X = 1
Output: 4
Explanation:
All subsets in which element 1 is present are:
{1}, {1, 2}, {1, 3}, {1, 2, 3}
Naive Approach:
The simple solution is to generate all possible subsets of a given set which are 2^n, where n is the size of the given set, and count the number of subsets in which element X is present.
Below is the implementation of the above approach.
C++
// C++ code to implement the above approach #include <bits/stdc++.h> using namespace std; int CountSubSet( int arr[], int n, int X) { // N stores total number of subsets int N = pow (2, n); int count = 0; // Generate each subset one by one for ( int i = 0; i < N; i++) { // Check every bit of i for ( int j = 0; j < n; j++) { // if j'th bit of i is set, // check arr[j] with X if (i & (1 << j)) if (arr[j] == X) count += 1; } } return count; } // Driver code int main() { int arr[] = { 4, 5, 6, 7 }; int X = 5; int n = sizeof (arr) / sizeof (arr[0]); cout << CountSubSet(arr, n, X); return 0; } |
Java
// Java code to implement the above approach class GFG { static int CountSubSet( int arr[], int n, int X) { // N stores total number of subsets int N = ( int ) Math.pow( 2 , n); int count = 0 ; // Generate each subset one by one for ( int i = 0 ; i < N; i++) { // Check every bit of i for ( int j = 0 ; j < n; j++) { // if j'th bit of i is set, // check arr[j] with X if ((i & ( 1 << j)) != 0 ) if (arr[j] == X) count += 1 ; } } return count; } // Driver code public static void main(String[] args) { int arr[] = { 4 , 5 , 6 , 7 }; int X = 5 ; int n = arr.length; System.out.print(CountSubSet(arr, n, X)); } } // This code is contributed by PrinciRaj1992 |
Python3
# Python3 code to implement the above approach def CountSubSet(arr, n, X) : # N stores total number of subsets N = 2 * * n; count = 0 ; # Generate each subset one by one for i in range (N) : # Check every bit of i for j in range (n) : # if j'th bit of i is set, # check arr[j] with X if (i & ( 1 << j)) : if (arr[j] = = X) : count + = 1 ; return count; # Driver code if __name__ = = "__main__" : arr = [ 4 , 5 , 6 , 7 ]; X = 5 ; n = len (arr); print (CountSubSet(arr, n, X)); # This code is contributed by AnkitRai01 |
C#
// C# code to implement the above approach using System; class GFG { static int CountSubSet( int []arr, int n, int X) { // N stores total number of subsets int N = ( int ) Math.Pow(2, n); int count = 0; // Generate each subset one by one for ( int i = 0; i < N; i++) { // Check every bit of i for ( int j = 0; j < n; j++) { // if j'th bit of i is set, // check arr[j] with X if ((i & (1 << j)) != 0) if (arr[j] == X) count += 1; } } return count; } // Driver code public static void Main(String[] args) { int []arr = { 4, 5, 6, 7 }; int X = 5; int n = arr.Length; Console.Write(CountSubSet(arr, n, X)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript code to implement the above approach function CountSubSet(arr, n, X) { // N stores total number of subsets let N = Math.pow(2, n); let count = 0; // Generate each subset one by one for (let i = 0; i < N; i++) { // Check every bit of i for (let j = 0; j < n; j++) { // if j'th bit of i is set, // check arr[j] with X if (i & (1 << j)) if (arr[j] == X) count += 1; } } return count; } // Driver code let arr = [4, 5, 6, 7]; let X = 5; let n = arr.length; document.write(CountSubSet(arr, n, X)); </script> |
8
Time complexity: O(n * 2^n).
Auxiliary Space: O(1), no extra space is required, so it is a constant.
Efficient solution:
- An efficient solution is to use the fact that every element of the set is present in exactly 2^(n-1) subsets.
- Here, in this solution, first, check whether the given value X is present in a given set of elements or not.
- If X is present, then compute and return 2^(n-1), (using modular exponentiation to compute power 2^n-1).
- Otherwise, return 0.
Below is the implementation of the above approach.
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; // Function to calculate (2^(n-1)) int calculatePower( int b, int e) { // Initially initialize answer to 1 int ans = 1; while (e > 0) { // If e is odd, // multiply b with answer if (e % 2 == 1) ans = ans * b; e = e / 2; b = b * b; } return ans; } // Function to count subsets in which // X element is present int CountSubSet( int arr[], int n, int X) { int count = 0, checkX = 0; // Check if X is present in // given subset or not for ( int i = 0; i < n; i++) { if (arr[i] == X) { checkX = 1; break ; } } // If X is present in set // then calculate 2^(n-1) as count if (checkX == 1) count = calculatePower(2, n - 1); // if X is not present in a given set else count = 0; return count; } // Driver Function int main() { int arr[] = { 4, 5, 6, 7 }; int X = 5; int n = sizeof (arr) / sizeof (arr[0]); cout << CountSubSet(arr, n, X); return 0; } |
Java
// Java implementation of above approach class GFG { // Function to calculate (2^(n-1)) static int calculatePower( int b, int e) { // Initially initialize answer to 1 int ans = 1 ; while (e > 0 ) { // If e is odd, // multiply b with answer if (e % 2 == 1 ) ans = ans * b; e = e / 2 ; b = b * b; } return ans; } // Function to count subsets in which // X element is present static int CountSubSet( int arr[], int n, int X) { int count = 0 , checkX = 0 ; // Check if X is present in // given subset or not for ( int i = 0 ; i < n; i++) { if (arr[i] == X) { checkX = 1 ; break ; } } // If X is present in set // then calculate 2^(n-1) as count if (checkX == 1 ) count = calculatePower( 2 , n - 1 ); // if X is not present in a given set else count = 0 ; return count; } // Driver code public static void main (String[] args) { int arr[] = { 4 , 5 , 6 , 7 }; int X = 5 ; int n = arr.length; System.out.println(CountSubSet(arr, n, X)); } } // This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of above approach # Function to calculate (2^(n-1)) def calculatePower(b, e) : # Initially initialize answer to 1 ans = 1 ; while (e > 0 ) : # If e is odd, # multiply b with answer if (e % 2 = = 1 ) : ans = ans * b; e = e / / 2 ; b = b * b; return ans; # Function to count subsets in which # X element is present def CountSubSet(arr, n, X) : count = 0 ; checkX = 0 ; # Check if X is present in # given subset or not for i in range (n) : if (arr[i] = = X) : checkX = 1 ; break ; # If X is present in set # then calculate 2^(n-1) as count if (checkX = = 1 ) : count = calculatePower( 2 , n - 1 ); # if X is not present in a given set else : count = 0 ; return count; # Driver code if __name__ = = "__main__" : arr = [ 4 , 5 , 6 , 7 ]; X = 5 ; n = len (arr); print (CountSubSet(arr, n, X)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of above approach using System; class GFG { // Function to calculate (2^(n-1)) static int calculatePower( int b, int e) { // Initially initialize answer to 1 int ans = 1; while (e > 0) { // If e is odd, // multiply b with answer if (e % 2 == 1) ans = ans * b; e = e / 2; b = b * b; } return ans; } // Function to count subsets in which // X element is present static int CountSubSet( int []arr, int n, int X) { int count = 0, checkX = 0; // Check if X is present in // given subset or not for ( int i = 0; i < n; i++) { if (arr[i] == X) { checkX = 1; break ; } } // If X is present in set // then calculate 2^(n-1) as count if (checkX == 1) count = calculatePower(2, n - 1); // if X is not present in a given set else count = 0; return count; } // Driver code public static void Main() { int []arr = { 4, 5, 6, 7 }; int X = 5; int n = arr.Length; Console.WriteLine(CountSubSet(arr, n, X)); } } // This code is contributed by AnkitRai01 |
Javascript
<script> // Javascript code to implement the above approach // Function to calculate (2^(n-1)) function calculatePower(b, e) { // Initially initialize answer to 1 let ans = 1; while (e > 0) { // If e is odd, // multiply b with answer if (e % 2 == 1) ans = ans * b; e = e / 2; b = b * b; } return ans; } // Function to count subsets in which // X element is present function CountSubSet(arr, n, X) { let count = 0, checkX = 0; // Check if X is present in // given subset or not for (let i = 0; i < n; i++) { if (arr[i] == X) { checkX = 1; break ; } } // If X is present in set // then calculate 2^(n-1) as count if (checkX == 1) count = calculatePower(2, n - 1); // if X is not present in a given set else count = 0; return count; } // Driver code let arr = [4, 5, 6, 7]; let X = 5; let n = arr.length; document.write(CountSubSet(arr, n, X)); // This code is contributed by shivanisinghss2110 </script> |
8
Time complexity: O(n)
Auxiliary Space: O(1), no extra space is required, so it is a constant.
Contact Us