Last Updated on March 23, 2022 by Ria Pathak
CONCEPTS USED:
Recursion
DIFFICULTY LEVEL:
Medium
PROBLEM STATEMENT(SIMPLIFIED):
Given a number N, your task is to print all possible permutations of its
Binary Representation.NOTE : Print the output in the lexicographically sorted form.
See original problem statement here
For Example :
Input : N = 5
Output : 011 101 110
Explanation :
Binary Representation of 5 is 101 and all permutations of it i.e. 011 101 110 are printed in a lexicographic order.SOLVING APPROACH:
- Start by finding the number of zeros and ones present in the
Binary Representationof N and store them inonesandzeros.- Initialize an empty string
strfor storing all such combinations one-by-one.- If
ones= 0, append all thezerostostrand print it. Else ifzeros= 0, append allonestostrand print it.- Else recursively keep appending a 0 to
strand reducezerosby 1. Similarly recursively keep appending a 1 tostrand reduceonesby 1 till allzerosandonesare appended in thestrand its size becomes equal to size of theBinary Representationof the number N.
ILLUSTRATION :
N = 5
Binary Representation of 5 = 101
Zeros = 1
Ones = 2
str = ""
Since Zeros and Ones both are not 0, append 0 to str and reduce Zeros by 1
str = "0"
Zeros = 0
Since Zeros = 0, append all remaining 1's to str
str = "011"
Ones = 0
Since Zeros = Ones = 0
print the str i.e. our first valid permutation of Binary Representation of 5.
Similarly print all such permutations recursively.SOLUTIONS:
#include <bits/stdc++.h>
using namespace std;
/* function for finding all such combinations */
void permutation(int no_ones, int no_zeroes, string accum,vector<string>&perm){
if(no_ones == 0){
for(int i=0;i<no_zeroes;i++){
accum += "0";
}
perm.push_back(accum);
return;
}
else if(no_zeroes == 0){
for(int j=0;j<no_ones;j++){
accum += "1";
}
perm.push_back(accum);
return;
}
permutation (no_ones - 1, no_zeroes, accum + "1",perm);
permutation (no_ones , no_zeroes - 1, accum + "0",perm);
}
int main(){
int t;
cin>>t;
while(t--){
int n, ones = 0, zeros = 0;
cin>>n;
/* finding number of zeros and ones in the number */
while(n>0)
{
if(n&1)
ones++;
else
zeros++;
n =n>>1;
}
//initializing an empty string
string append = "";
//vector of strings to store all the combinations
vector<string>perm;
permutation(ones, zeros, append, perm);
/* sort all combinations in ascending order */
sort(perm.begin(),perm.end());
for(int i=0;i<perm.size();i++)
cout<<perm[i]<<" ";
}
}
import java.util.*;
import java.io.*;
public class Main {
/* function for finding all such combinations */
static void permutation(int no_ones, int no_zeroes, String accum, ArrayList<String> perm){
if(no_ones == 0){
for(int i=0;i<no_zeroes;i++){
accum += "0";
}
perm.add(accum);
return;
}
else if(no_zeroes == 0){
for(int j=0;j<no_ones;j++){
accum += "1";
}
perm.add(accum);
return;
}
permutation (no_ones - 1, no_zeroes, accum + "1",perm);
permutation (no_ones , no_zeroes - 1, accum + "0",perm);
}
public static void main(String args[]) throws IOException {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t != 0){
int n = sc.nextInt();
int ones = 0, zeros = 0;
/* finding number of zeros and ones in the number */
while(n>0)
{
if(n%2 == 0)
zeros++;
else
ones++;
n /= 2;
}
//initializing an empty string
String append = "";
//vector of strings to store all the combinations
//vector<string>perm;
ArrayList<String> perm = new ArrayList<String>();
permutation(ones, zeros, append, perm);
/* sort all combinations in ascending order */
Collections.sort(perm);
for(int i=0;i<perm.size();i++)
System.out.print(perm.get(i) + " ");
System.out.println();
t--;
}
}
}
}
def permutation(no_ones, no_zeroes, accum, perm): if(no_ones == 0): for i in range(no_zeroes): accum = accum + "0" perm.append(accum) return elif(no_zeroes == 0): for j in range(no_ones): accum = accum + "1" perm.append(accum) return permutation (no_ones - 1, no_zeroes, accum + "1", perm) permutation (no_ones , no_zeroes - 1, accum + "0", perm) for _ in range(int(input())): n = int(input()) ones, zeros = 0, 0 while n>0: if n & 1: ones += 1 else: zeros += 1 n = n >> 1 a = "" perm = [] permutation(ones, zeros, a, perm) perm.sort() print(*perm)
[forminator_quiz id="1001"]
This article tried to discuss Recursion. Hope this blog helps you understand and solve the problem. To practice more problems on Recursion you can check out MYCODE | Competitive Programming.
If one consider solving it by using strings then it could be made easier.
#include
using namespace std;
void binaryPattern(string op, int zero, int one)
{
if (!one && !zero)
{
cout << op <0)
{
if (n%2 == binary) count++;
n/=2;
}
return count;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while(t–)
{
int n;
cin >> n;
int zero = getCount(n, 0);
int one = getCount(n, 1);
binaryPattern(“”, zero, one);
cout << endl;
}
}