[Solved] Calculate the sum with minimum usage of numbers


Here’s a hint:

23 : 11 + 11+ 1 ( 3 magic numbers)

120: 110+ 10 (2 magic numbers)

The highest digit in the target number is the answer, since you need exactly k magic numbers (all having 1 in the relevant position) in order for the sum to contain the digit k.

So the algorithm would start by splitting the target sum into digits. For example, if the input is 3052, you should create the following array:

int[] digits = {3,0,5,2};

While you split the target sum into digits, you can also find the largest digit.

int max = 5;

Now we know we need 5 magic numbers, and all that remains is actually finding them. You can do so by iterating over the array of the digits max times.

In each iteration you create a single magic number whose 1 digits correspond with positive values of the array. You also decrement those values.

1st iteration:

3,0,5,2 ->  create magic number 1011 & decrement the array values to 2,0,4,1

2nd iteration:

2,0,4,1 ->  create magic number 1011 & decrement the array values to 1,0,3,0

3rd iteration:

1,0,3,0 ->  create magic number 1010 & decrement the array values to 0,0,2,0

4th iteration:

0,0,2,0 ->  create magic number   10 & decrement the array values to 0,0,1,0

5th iteration:

0,0,1,0 ->  create magic number   10 & decrement the array values to 0,0,0,0

We are done, the magic numbers are 1011 + 1011 + 1010 + 10 + 10 = 3052.

4

solved Calculate the sum with minimum usage of numbers