Minimal sum of sums in C

Question

Here’s a run down of the problem:

We are given an int array. We need to compress the array into a single int. Each compression is adding two of the ints together. The value returned from a compression gets pushed back into the “needs to be compressed” group and added to a running sum for all the compressions. So the goal is to have a minimal sum once the array is completely compressed. Here’s an example if I’m not making sense:

————

To Be Compressed                Runningsum   sum
[5, 12, 9, 15] -> 5 + 9 = 14.         0+14 = 14
[14, 12, 15] -> 14 + 12 = 26.        14+26 = 40
[26, 15] -> 26 + 15 = 41.            40+41 = 81
[41] -> Done 

So here 81 is the solution.

————

And just for completeness. Here’s a wrong solution:

To Be Compressed                Runningsum   sum
[5, 12, 9, 15] -> 5 + 12 = 17.        0+17 = 17
[17, 9, 15] -> 9 + 15 = 24.          17+24 = 41
[17, 24] -> 17 + 24 = 41.            41+41 = 82
[41] -> Done

So here 82 is not the optimal sum of sums.

————

I understand how to do this brute force O(n^2) by doing a double for loop and finding the next minimum in the array each inner loop. Then in the outer loop the running sum is set to itself + the min just found and then the running sum is added to the total sum.

    findminimum() //5
runningsum=runningsum + 5
sum=0
    findminimum() //9
runningsum=runningsum + 9  //5+9=14
sum+=runningsum            //0+14=14
    findminimum() //12
runningsum=runningsum + 12 //14+12=26
sum+=runningsum            //14+26=40
    findminimum() //15
runningsum=runningsum + 15 //26+15=41
sum+=runningsum            //40+41=81

return sum

This works but obviously O(n^2) is not the best.

Next, you could mergesort the array. Since the array is sorted we wouldn't have to do the 2nd for loop that was finding the next min aka findminimum() above. So we can just do the runningsum and sum math in a single for loop. This would O(nlog(n)).

So my question, do you all see any way to do this in O(n) or does nlogn seem to be the best possibility? There might be some math formula used to solve this that I’m just not familiar with.

If anything is unclear I’m glad to specify. Thanks for you time!

Answer 1

If indeed your minimum runtime is bound by your sort, then a classic comparison sort will net you provably at best O(nlogn).

Keyword there is a "comparison" sort.

If you're at all familiar with linear time sorts, those may come in useful for you here.

This link describes what's called a counting sort for example.

It does a (much) better job of explaining than what I can do here. Essentially, you allocate an array of size max(arrtoMinSum), then for every element in arrToMinSum, you increment the array value at that index. After a cumulative sum on that allocated array, you then iterate through your original array, and using the values in your allocated array as indices for storing each of the values in your original array in a final output array. I highly recommend you read through it, rather than implementing based on my explanation.

Since you create an array of size max(arrToMinSum), and iterate through both it AND your original array, your runtime will be O(max(max(arrToMinSum),n). This is (in many to most cases) faster than a comparison sort at the expense of higher memory usage.

Answer 2

I think your optimised approach is not enough. Imagine the following input:

[4, 5, 7, 8, 10]

In this case you already have an ordered list. Let's also assume it is implemented as a binary tree - so searching is O(log(n)).

Now you add 4 and 5. The result 9 is not am operand of the next sum operation. So you have to insert it in the sorted list, which is O(log(n)).

Therfore even with an already sorted list you have O(n * log(n)).

So the reason you can't reach a complexity of O(log(n)) is, that your sum n relies on sum n - 1 and the ordering of that result in the rest of your inputs. Therfore an approach of adding n * a[0] + (n - 1) * a[1]... cannot be successful.