Mike and Binary Number

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:


#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.

Leave a Reply

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