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

Previous post Check Palindrome
Next post Matrix and combination

Leave a Reply

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