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!
Recursion Interview Programming

Mike and Binary Number

Deepanshu

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:

  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:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#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]<<" ";
}
}
#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]<<" "; } }
#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]<<" ";
   }
}
Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
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--;
}
}
}
}
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--; } } } }
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--;
    }
  }
}
}
Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
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)
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)
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. 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;
    }

    }

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

Close

Related Post