2

A number is called as binary-decimal if all the digits in the number should be either ‘1’ or ‘0’. Any number can be written as a sum of binary-decimals. Our task is to find the minimum number of binary-decimals to represent a number.

Input : 32 Output : 10 11 11

Input : 120 Output : 10 110

What could be an efficient solution to this?

3 Answers 3

5

take for example

54321 the answer is

11111

11110

11100

11000

10000

so consider it as a m*n matrix where m is maximum value of the digit in given number and n is number of digits. Then fill the columns with number of 1's equal to the value of digit corresponding to that column and rest with 0's.

        #include<iostream>

        using namespace std;
        int max(int arr[],int c)
        {
            int max=arr[0];
            for(int i=1;i<c;i++){
                if(arr[i]>max){
                    max=arr[i];
                }
            }
            return max;
        }
        int main() {
            int n,x,c=0,i=0,j=0;
            cin>>n;
            x=n;
            while(n!=0){
                n=n/10;
                c++;
            }
            int *a=new int[c];

            while(x!=0){
                a[i]=x%10;
                x=x/10;
                i++;
            }
            int r=max(a,c);
            int ans[r][c];
            for(int i=0;i<c;i++)
            {
                for(int j=0;j<r;j++)
                {
                    if(a[c-i-1]!=0){
                        ans[j][i]=1;
                        a[c-i-1]--;
                    }
                    else
                        ans[j][i]=0;
                }
            }
            for(i=0;i<r;i++){
                for(j=0;j<c;j++){
                    cout<<ans[i][j];
                }
                cout<<"\n";
            }

            }
1
  • This is the best solution I have seen for this question so far. Good one. Thanks. Oct 18, 2018 at 15:48
0

I have solved this using DP. May not be as good as the previous one. But this could be another approach.

import java.util.ArrayList;
import java.util.*;
class Deci_binary
{
public static void main(String ars[])
{
    Scanner sc=new Scanner(System.in);
    Deci_binary Db=new Deci_binary();
    Db.deci_binary(sc.nextInt());
}
public void deci_binary(int input)
{
    String input_string=input+"";
    int length=input_string.length();
    ArrayList<Integer> combination=combination(length);
    ArrayList dp[]=new ArrayList[input+1];
    ArrayList<Integer> empty=new ArrayList<Integer>();
    dp[0]=empty;
    int combination_size=combination.size();
    for(int i=1;i<=input;i++)
    {
        dp[i]=null;
        for(int j=0;j<combination_size;j++)
        {
            int combination_get=combination.get(j);
            if(i>=combination_get)
            {
                ArrayList<Integer> previous=new ArrayList<Integer>(dp[i-combination_get]);
                previous.add(combination_get);
                dp[i]=min(dp[i],previous);
            }
            else{
                break;
            }
        }
    }
    System.out.println(dp[input]);

}
public ArrayList<Integer> min(ArrayList<Integer> first,ArrayList<Integer> second)
{
    if(first==null)
    {
        return second;
    }
    else{
        int first_size=first.size();
        int second_size=second.size();
        if(first_size<second_size)
        {
            return first;
        }
        else{
            return second;
        }
    }
}
public ArrayList<Integer> combination(int number)//this will give all the combinations of binary number having x number of digits
{

    int last_number=(int)Math.pow(2,number);
    ArrayList<Integer> combination=new ArrayList<Integer>(last_number-1);
    for(int i=1;i<last_number;i++)
    {
        combination.add(Integer.parseInt(Integer.toBinaryString(i)));            
    }
    return combination;
}
}
0

The simplest solution could be return the highest digit from the number. For example : The answer to 82734 is

11111

11111

10111

10101

10100

10100

10100

10000

Below is a c++ solution for this.

int solve(int n) {
    string n_str = to_string(n);
    return *max_element(n_str.begin(),n_str.end()) - '0';
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.