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

Prepbytes

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.

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

Leave a Reply

Close

Related Post