## Sunday, December 25, 2016

### Minimum sum of two numbers formed from digits of an array - GeeksforGeeks

Minimum sum of two numbers formed from digits of an array - GeeksforGeeks
Given an array of digits (values are from 0 to 9), find the minimum possible sum of two numbers formed from digits of the array. All digits of given array must be used to form the two numbers.

Since we want to minimize the sum of two numbers to be formed, we must divide all digits in two halves and assign half-half digits to them. We also need to make sure that the leading digits are smaller.
We build a Min Heap with the elements of the given array, which takes O(n) worst time. Now we retrieve min values (2 at a time) of array, by polling from the Priority Queue and append these two min values to our numbers, till the heap becomes empty, i.e., all the elements of array get exhausted. We return the sum of two formed numbers, which is our required answer.

`    ``public` `static` `long` `solve(``int``[] a)`
`    ``{`
`        ``// min Heap`
`        ``PriorityQueue<Integer> pq = ``new` `PriorityQueue<Integer>();`

`        ``// to store the 2 numbers formed by array elements to`
`        ``// minimize the required sum`
`        ``StringBuilder num1 = ``new` `StringBuilder();`
`        ``StringBuilder num2 = ``new` `StringBuilder();`

`        ``// Adding elements in Priority Queue`
`        ``for` `(``int` `x : a)`
`            ``pq.add(x);`

`        ``// checking if the priority queue is non empty`
`        ``while` `(!pq.isEmpty())`
`        ``{`
`            ``num1.append(pq.poll()+ ``""``);`
`            ``if` `(!pq.isEmpty())`
`                ``num2.append(pq.poll()+ ``""``);`
`        ``}`

`        ``// the required sum calculated`
`        ``long` `sum = Long.parseLong(num1.toString()) +`
`                   ``Long.parseLong(num2.toString());`

`        ``return` `sum;`
`    ``}`

Read full article from Minimum sum of two numbers formed from digits of an array - GeeksforGeeks