0
\$\begingroup\$

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/

\$\endgroup\$
  • 4
    \$\begingroup\$ Can you show an example of the minimum sum, and how this would be different from the sum of elements? \$\endgroup\$ – AJNeufeld Jul 8 at 4:20
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – AJD Jul 8 at 5:48
  • 1
    \$\begingroup\$ It could be a misinterpretation of this problem where the sums of the removed elements are accumulated in each step. \$\endgroup\$ – Martin R Jul 8 at 6:39
  • \$\begingroup\$ 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. \$\endgroup\$ – Sam Furlong Jul 8 at 17:20
  • 1
    \$\begingroup\$ 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?!) \$\endgroup\$ – greybeard Jul 9 at 8:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.