Finding Deci-Binary for given input

Question

Can anybody have solution for finding Deci-Binary ( Decimal numbers contains 0 and 1 like 100 111 101 ,.etc and numbers like 12, 13 and 5551 are not Deci-Binary)

Numbers used here are decimal only nothing is in Binary format.

Output is not in Binary format. Sum of all numbers in output should be same as Input. For example below Input is Decimal 4 and output is decimals 1,1,1 and 1. When adding all the output we can get the input.

If input is 11 then, that is a deci-binary so we don't want to convert it. so the output will be same as input 11.

For input 4
Output should be 1 1 1 1

Other scenarios as below

IP: 4
OP: 1 1 1 1

IP: 21
OP: 10 11 

IP: 11
OP: 11

IP: 100 
OP: 100 

IP: 99
OP: 11 11 11 11 11 11 11 11 11

I tried, could not resolve it.

EDIT: This is not duplicate of Finding shortest combinations in array/sequence that equals sum my question is not a sub-set problem and completly different form that question

It seems there are various different definitions of "decibinary". What's yours? — Klitos Kyriacou
– Klitos Kyriacou, Commented Apr 30, 2019 at 7:07
Considering minimum split count, the problem can be reduced to Min-Coin_Change-Problem ("algorithmist.com/index.php/Min-Coin_Change"). see stackoverflow.com/questions/9964289/… With "coins" [1,10,11,100,101,110,111,1000,1001,1010,1011,1100,...]" The approach requires to build the "coin"-list up to value and feed it into the algorithm. — SirFartALot
– SirFartALot, Commented Apr 30, 2019 at 10:02

talex · Accepted Answer · 2019-04-30 07:52:12Z

Another solution with slightly different approach

public static void main(String[] args) {
    printDeciBin(1);
    printDeciBin(4);
    printDeciBin(10);
    printDeciBin(11);
    printDeciBin(19);
    printDeciBin(21);
    printDeciBin(99);
    printDeciBin(100);
}

public static void printDeciBin(int number) {
    System.out.println(String.format("%d -> %s", number, findDeciBins(number).stream()
            .map(Object::toString)
            .collect(Collectors.joining(" "))));
}

static Collection<Integer> findDeciBins(int number) {
    List<Integer> l = new ArrayList<>();
    while (number != 0) {
        l.add(number % 10);
        number /= 10;
    }
    Collections.reverse(l);


    List<Integer> result = new ArrayList<>();
    while (true) {
        boolean stop = true;
        int curr = 0;
        for (int i = 0; i < l.size(); i++) {
            curr *= 10;
            if (l.get(i) != 0) {
                curr++;
                l.set(i, l.get(i) - 1);
                stop = false;
            }
        }
        if (stop){
            break;
        }
        result.add(curr);
    }

    return result;
}

SirFartALot · Accepted Answer · 2019-04-30 07:44:56Z

2

Seems the logic here is a bunch of written binaray numbers (consisting of 1 or 0) are added as decimal numbers until the sum results in the requested number.

So all you have to do is to find the maximum possible "deci-binary" and do this as long as you have your sum.

To print or to find the maximum decbinary, you will need the "length" of the current decibinary, log10 will help.

Java-Code:

package de.test.lang.stackexchange;

import java.util.Collection;
import org.apache.commons.lang.StringUtils;

public class DeciBins {

    public static void main(String[] args) {
        printDeciBin(1);
        printDeciBin(4);
        printDeciBin(10);
        printDeciBin(11);
        printDeciBin(19);
        printDeciBin(21);
        printDeciBin(99);
        printDeciBin(100);
    }

    @SuppressWarnings("UseOfSystemOutOrSystemErr")
    public static void printDeciBin(int number) {
        System.out.println(String.format("%d -> %s", number, StringUtils.join(findDeciBins(number), " ")));
    }

    // finds the array of deciBins by determining the maximum possible
    // deciBin and subtract it, until 0.
    static Collection<Integer> findDeciBins(int number) {
        Collection<Integer> decis = new java.util.ArrayList<>();
        int deciBin = number;
        while (deciBin > 0) {
            int y = find_maximum_decibinary(deciBin); // (e.g. for 99 => 11)
            deciBin -= y;
            decis.add(y);
        }
        return decis;
    }

    // finds the maximum decibin by determining the max length and substract 1
    // until the val is smaller or equal the requested value x.
    static int find_maximum_decibinary(int x) {
        int l = (int) Math.ceil(Math.log10(x + 1));
        int currMax = (1 << l) - 1;
        while (currMax > 0) {
            int curVal = Integer.parseInt(Integer.toBinaryString(currMax));
            if (curVal <= x) {
                return curVal;
            }
            currMax--;
        }
        return 1;
    }
}

edited Apr 30, 2019 at 7:44

answered Apr 30, 2019 at 6:55

SirFartALot

1,2257 silver badges25 bronze badges

4 Comments

talex Over a year ago

Why 21 -> 10 11? Shouldn't it be 11 10 then?

SirFartALot Over a year ago

Valid argument. Dunno, maybe one can sort the array of decibinaries afterwards.

talex Over a year ago

Or probably just reverse the list. Anyway it is not correct answer until author explains what he want to achieve.

saravanakumar Over a year ago

@talex order is not a matter. Out put is fine.

Collectives™ on Stack Overflow

Finding Deci-Binary for given input

2 Answers 2

Comments

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related