Recently a friend of mine gave me a problem to solve. You are given n numbers and initialize sum=0. You are doing steps until there is only one number left. In every step you take two numbers a and b, remove them from the set, add (a+b) to sum (sum+=a+b) and insert number (a+b) to our set. What is the smallest sum that you can achieve after this process?
Example: you are given numbers (1,2,3) and sum=0
1. You may take (1,2) then sum=3 or (2,3) then sum=5 or (1,3) then sum=4
2. Now you have numbers (3,3) or (5,1) or (4,2) and after this step sums are respectively sum=9 or sum=11 or sum=10
3. So the lowest sum you can achieve is 9
So I came up with a solution. In each step you take two smallest numbers. But I cannot prove that this strategy is correct. Are you able to prove or discard it?
Yes, I believe your logic might work! Although, the complexity of the solution might be little high after all find two minimum numbers and repeating the same process might require approx. (n square) operations!
You can do it in O(n*logn), just keep those numbers in set structure. Then taking, erasing and inserting takes in each step O(logn).
The proof is simple:
Assume n numbers in the array:
You can prove that 1 number will be added n times
1 number will be added n-1 times
and so on till
1 number will be added 1 time
So you have to minimise sum,where
sum = n*(a[x1]) + (n-1)*(a[x2]) + .... + 1*(a[xn])
Since we must minimise, obvious solution to sort the array and set xi = i and find sum
Hope it is clear
Chuck it. I misunderstood the question
Yes, this is correct. This is a well-known technique actually: Huffman coding. You can find a proof in the article.
I don't see a proof there.
It seems that you're right, I also didn't find it there. But there's one on CLRS3, pages 433-434.
The key idea is that each possible encoding corresponds to an arrangement of vertices in a (complete**) binary tree. It's not hard to notice that there exists an optimal encoding in which the two lower-valued nodes are siblings. You can combine these two nodes, inductively obtain an optimal encoding for the remaining ones and then un-combine them — this results in an optimal encoding for the original set of vertices.
** Technically the tree doesn't need to be complete, but this is always the case for an optimal encoding.
here is logic. however, we always do n — 1 operation. For each of operation we must take two min numbers and add sum of numbers has been token result, after that our result will be minimize...