# Mike and Binary Number

Recursion

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:

1. Learn master data structures and algorithms online and Start by finding the number of zeros and ones present in the `Binary Representation` of N and store them in `ones` and `zeros`.

2. Initialize an empty string `str` for storing all such combinations one-by-one.

3. If `ones` = 0, append all the `zeros` to `str` and print it. Else if `zeros` = 0, append all `ones` to `str` and print it.

4. Else recursively keep appending a 0 to `str` and reduce `zeros` by 1. Similarly recursively keep appending a 1 to `str` and reduce `ones` by 1 till all `zeros` and `ones` are appended in the `str` and its size becomes equal to size of the `Binary Representation` of 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";
}
return;
}
else if(no_zeroes == 0){
for(int j=0;j<no_ones;j++){
accum += "1";
}
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--;
}
}
}
```