Reduce array by adding elements

You array will be always reduces to the sum of all its elements. The "cost" of this reduction may vary though. The minimum "cost" could be achieved by adding two minimum elements that currently exist in the array.

Min heap can be used to solve this problem very efficiently. Here's an example in java.

    public int[] sumAndCost(Integer[] arr) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Arrays.asList(arr));
        int sum = priorityQueue.poll();
        int cost = 0;
        while (!priorityQueue.isEmpty()) {
            int currentElement = priorityQueue.poll();
            if (currentElement < sum) {
                priorityQueue.add(sum);
                sum = currentElement;
            } else {
                sum += currentElement;
                cost += sum;
                continue;
            }

            sum += priorityQueue.poll();
            cost += sum;
        }

        return new int[] {sum, cost};
    }

It returns both the sum and the cost for any given array.

Conditional statement may seen a bit uncessary but it somewhat improves our runtime.

Credits to @tobias_k for fantastic explanation.My solution using just list,

`

def reduction(num):
    a= []
    cost = 0
    while len(num) > 1:
        first = num.pop(0)
        second = num.pop(0)
        cost += first + second
        num = [first+second] + num
    print(cost)

`

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]));

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.