# Minimum sum of elements, taken 2 at a time

Update: I had not recalled the question correctly and ended up with the wrong question. I have now updated the question and the solution:

The question is: Given an array of integers say [8,4,6,12,10] You can pop any two elements at a time and place the sum (chosen sum) back into the array. Repeating until a single element (final sum) is remaining. The task is to minimize the sum of these chosen sums in the end.

My approach is:

• Pop the two elements with lowest value in the array, push the sum back.
• Repeat this until a single element is remaining.
• Maintain a sums, which maintains the running sum

My solution is as follows:

1. Sort the array
2. Pop first two elements, add them, get the sum
3. Place the sum in the array in such a way that it remains sorted (to avoid sorting again)
4. Repeat steps 2 and 3 until we have less than two elements in the array

JavaScript Code:

  function join(parts, sums) {
if(parts.length < 2) {
return sums
}
sum = parts[0] + parts[1]
sliced = parts.slice(2)
placed = place(sliced, sum)
sums = sums + sum
return join(placed, sums)
}

function place(arr, x) {
index = 0
for(i=0;i<arr.length;i++) {
if(arr[i]>x) {
index = i
break
}
}
first = arr.slice(0,i)
second = arr.slice(i)
return [...first,x,...second]
}
function process(parts) {
parts.sort((a,b)=>a>b)
return join(parts, 0)
}
process([8,4,6,12,10])


Is this best possible approach? Can you think of any better optimized approach?

Update: The complexity is O(nlog n) (sort - best case) + O(n)

As pointed out in the comments, the ideal solution would be to use a priority queue: https://www.geeksforgeeks.org/minimize-the-sum-calculated-by-repeatedly-removing-any-two-elements-and-inserting-their-sum-to-the-array/

• Can you show an example of the minimum sum, and how this would be different from the sum of elements? – AJNeufeld Jul 8 '19 at 4:20
• No matter how you pop them, the sum will always be the same - unless you have different definition of 'sum'. This is the basis for the commutative and distributive laws of arithmetic that we operate under. – AJD Jul 8 '19 at 5:48
• It could be a misinterpretation of this problem where the sums of the removed elements are accumulated in each step. – Martin R Jul 8 '19 at 6:39
• The geeks for geeks page gives you your answer- the best solution you can get in terms of run time would be using a priority queue implemented by some sort of min heap (likely Fibonacci). If you are interested in why this is faster comment and I can write something up as the answer. – Sam Furlong Jul 8 '19 at 17:20
• Let me plug that this is pretty much what is done constructing a static Huffman code - the part about using sorting and a simple queue instead of a priority queue starts with If the symbols are sorted by probability, there is a linear-time (O(n)) method. (An older comment somehow dissipated?!) – greybeard Jul 9 '19 at 8:28