Reduce array by adding elements

Question

I came across this question in a test.

Given an array, reduce the array to a single element with minimum cost. For reducing, remove two elements from the array, add those two numbers and keep the sum back in the array. The cost of each operation is the sum of the elements removed in that step.

Example, let the array A = [1,2,3]

Then, we can remove 1 and 2, add both of them and keep the sum back in array. Cost of this step would be (1+2) = 3.

So A = [3,3], Cost = 3

In second step, we can remove both elements from the array and keep the sum back in array again. Cost of this step would be 3 + 3 = 6.

So, A = [6], Cost = 6

So total cost turns out to be 9 (6+3).

I tried sorting the array, and adding the elements from decreasing to increasing, but it fails if there are duplicate elements.

Pseudo code of my algorithm

sort(Array)
cost = 0
for(i=0; i<Array.length - 1; i++) {
   Array[i+1] = Array[i] + Array[i+1]
   cost = cost + Array[i+1]
}

The algorithm mentioned above was not working. I came up with a possible case where it may fail. If the Array = [5, 5, 5, 5], then Cost = 45, according to the above algorithm.

However if we sum the first two elements and last two elements, and then sum the remaining two elements, then the total cost turns out to be 40. (In first step, cost = 10*2, and in next step another 20)

What could be a efficient algorithm for this?

Answer 1

You were on the right track with sorting the array and summing the lowest elements first. The problem is: The sum of the two lowest elements could be greater than the next element after those, so you can't just put it in the front. But it can also be smaller than the last element, so you can't put it in the back, either. You have to put the sum into just the place it belongs w.r.t. the sorting.

Example: If your list is [1, 1, 3, 3], then 1+1 should be put in the front, i.e. [2, 3, 3], but if we have [2, 2, 3, 3], then the sum 2+2 has to be put in the back [3, 3, 4], and for [2, 2, 3, 5] is has to be put in the middle position, i.e. [3, 4, 5].

A simple way to do this is using a heap structure. Those are available in most languages and provide methods for getting and removing the smallest element, and for inserting an element in the right place. Here's an example in Python:

import heapq
def reduce_sum(lst):
    heapq.heapify(lst)
    s = 0
    while len(lst) > 1:
        first = heapq.heappop(lst)
        second = heapq.heappop(lst)
        s += first + second
        heapq.heappush(lst, first + second)
    return s

reduce_sum([1,2,3])      # 9
reduce_sum([5, 5, 5, 5]) # 40

And if you can not use Heaps, you can still iterate the array to find the right place to put the summed element, or use binary search to do so faster.

Answer 2

First, sort the array.

Second, loop this step until only two elements remain in the array.

• Get a new value by summing the first two elements of the array
• Put this new value into the array at the proper position

Third, return the sum of two elements that are remained in the array.

function sortedIndex(array, value) {
  let low = 0, high = array.length;

  while (low < high) {
    let mid = (low + high) >>> 1;
    if (array[mid] < value) low = mid + 1;
    else high = mid;
  }
  return low;
}

function reductionCost(num) {
  let cost = 0;
  num.sort((a, b) => {
    return a - b;
  });

  while (num.length > 2) {
    const newValue = num.shift() + num.shift();
    cost += newValue;
    const newIndex = sortedIndex(num, newValue);
    num.splice(newIndex, 0, newValue);
  }
  return cost + num[0] + num[1];
}

console.log(reductionCost([1, 2, 3]));
console.log(reductionCost([5, 5, 5, 5]));