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

You can check this link : https://www.geeksforgeeks.org/java-program-for-decimal-to-binary-conversion/ — Pawan Tiwari, Apr 30 '19 at 06:52
It seems there are various different definitions of "decibinary". What's yours? — Klitos Kyriacou, Apr 30 '19 at 07:07
If your intention is to convert decimal inputs into binary outputs then your test data is flawed i.e. the number ```4``` is ```100``` in decimal. Thus please clarify your question or check your test data. — BeWu, Apr 30 '19 at 07:12
For clarification: The input needs to be be divided in groups of decimals that only consist of 1 and 0, is that assumption right? How should multiple possible solutions be handled? I.e. the input ```97``` would be valid as ```11 11 11 11 11 11 11 10 10``` and ```11 11 11 11 11 11 11 11 1 1 1 1 1 1 1 1 1``` and many more different combinations of 1, 10 and 11. Also consider adding a definition of deci-binaries as you need it (as suggested by Klitos) because that term is ambiguous. — BeWu, Apr 30 '19 at 09:09
@BeWu Yes correct. The answer should be minimum split count. First one in your example is correct. I came to know this term in an interview. So I wrote it as I heard. Sorry if anything wrong. — saravanakumar, Apr 30 '19 at 09:45
Considering minimum split count, the problem can be reduced to Min-Coin_Change-Problem ("https://www.algorithmist.com/index.php/Min-Coin_Change"). see https://stackoverflow.com/questions/9964289/finding-shortest-combinations-in-array-sequence-that-equals-sum 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, Apr 30 '19 at 10:02
Possible duplicate of [Finding shortest combinations in array/sequence that equals sum](https://stackoverflow.com/questions/9964289/finding-shortest-combinations-in-array-sequence-that-equals-sum) — SirFartALot, Apr 30 '19 at 10:47

score 3 · Accepted Answer · answered Apr 30 '19 at 07:52

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 · Answer 2 · 2019-04-30T07:44:56.873

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

Valid argument. Dunno, maybe one can sort the array of decibinaries afterwards. — SirFartALot, Apr 30 '19 at 07:01
Or probably just reverse the list. Anyway it is not correct answer until author explains what he want to achieve. — talex, Apr 30 '19 at 07:18

Finding Deci-Binary for given input

2 Answers2