  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Mike and Binary Number

Last Updated on March 23, 2022 by Ria Pathak 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. 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--;
}
}
}
}
```
```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.

## One thought on “Mike and Binary Number”

1. Shubham Bonde says:

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;
}

}