Given an integer N, the task is to print all the subsets of the set formed by the set bits present in the binary representation of N.
Examples:
Input: N = 5
Output: 5 4 1
Explanation:
Binary representation of N is “101”, Therefore all the required subsets are {“101”, “100”, “001”, “000”}.Input: N = 25
Output: 25 24 17 16 9 8 1
Explanation:
Binary representation of N is “11001”. Therefore, all the required subsets are {“11001”, “11000”, “10001”, “10000”, “01001”, “01000”, “0001”, “0000”}.
Naive Approach: The simplest approach is to traverse every mask in the range [0, 1 << (count of set bit in N)] and check if no other bits are set in it except for the bits in N. Then, print it.
Time Complexity: O(2(count of set bit in N))
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized by only traversing the submasks which are the subset of mask N.
- Suppose S is the current submask which is the subset of mask N. Then, it can be observed that by assigning S = (S – 1) & N, the next submask of N can be obtained which is less than S.
- In S – 1, it flips all the bits present on the right of the rightmost set bit including rightmost set bit of S.
- Therefore, after performing Bitwise & with N, a submask of N is obtained.
- Therefore, S = (S – 1) & N gives the next submask of N which is less than S.
Follow the steps below to solve the problem:
- Initialize a variable, say S = N.
- Iterate while S > 0 and in each iteration, print the value of S.
- Assign S = (S – 1) & N.
Below is the implementation of the above approach:
C++
// C++ Program for above approach#include <bits/stdc++.h>using namespace std;// Function to print the submasks of Nvoid SubMasks(int N){ for (int S = N; S; S = (S - 1) & N) { cout << S << " "; }}// Driver Codeint main(){ int N = 25; SubMasks(N); return 0;} |
Java
// Java Program for above approachimport java.util.*;class GFG{ // Function to print the submasks of Nstatic void SubMasks(int N){ for (int S = N; S > 0; S = (S - 1) & N) { System.out.print(S + " "); }}// Driver Codepublic static void main(String args[]){ int N = 25; SubMasks(N);}}// This code is contributed by SURENDRA_GANGWAR. |
Python3
# Python3 program for the above approach# Function to print the submasks of Ndef SubMasks(N) : S = N while S > 0: print(S,end=' ') S = (S - 1) & N# Driven Codeif __name__ == '__main__': N = 25 SubMasks(N) # This code is contributed by bgangwar59. |
C#
// C# program for the above approachusing System;class GFG{// Function to print the submasks of Nstatic void SubMasks(int N){ for (int S = N; S > 0; S = (S - 1) & N) { Console.Write(S + " "); }}// Driver Codestatic public void Main(){ int N = 25; SubMasks(N);}}// This code is contributed by Code_hunt. |
Javascript
<script>// JavaScript program of the above approach// Function to print the submasks of Nfunction SubMasks(N){ for (let S = N; S > 0; S = (S - 1) & N) { document.write(S + " "); }} // Driver Code let N = 25; SubMasks(N);</script> |
25 24 17 16 9 8 1
Time Complexity: O(2(count of set bit in N))
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
