Calculate the sum with minimum usage of numbers

by

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.

More Related Contents:

  1. time complexity of recursion function
  2. Solve T(n)=T(n-1)+2n by backwards iteration method
  3. How to convert floats to human-readable fractions?
  4. Subset Sum algorithm
  5. How to calculate an angle from three points? [closed]
  6. How to implement a queue using two stacks?
  7. Graph auto-layout algorithm
  8. Linear time algorithm for 2-SUM
  9. Which parallel sorting algorithm has the best average case performance?
  10. Is there an algorithm for color mixing that works like mixing real colors?
  11. finding if two words are anagrams of each other
  12. Create a random permutation of 1..N in constant space
  13. O(klogk) time algorithm to find kth smallest element from a binary heap
  14. Compute rank of a combination?
  15. Calculating permutations in F#
  16. generate all partitions of a set [closed]
  17. Efficiently selecting a set of random elements from a linked list
  18. Find if a point is inside a convex hull for a set of points without computing the hull itself
  19. RGB value base color name
  20. Given Prime Number N, Compute the Next Prime?
  21. Variation on knapsack – minimum total value exceeding ‘W’
  22. Path generation for non-intersecting disc movement on a plane
  23. When is each sorting algorithm used? [closed]
  24. Difference between Big-Theta and Big O notation in simple language
  25. How can I perform Collision Detection on rotated rectangles? [closed]
  26. Find the pair across 2 arrays with kth largest sum
  27. 3-PARTITION problem
  28. Binary tree level order traversal
  29. algorithm to check a connect four field
  30. What is the most efficient way to encode an arbitrary GUID into readable ASCII (33-127)?

Leave a Comment