Question

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.

Answer 1

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)

PLEASE MAKE ME AS A BRAINLIST ANSWER

Answer 2

Answer:

• Consider an array A = [10,20,30,40]

• we can remove 10 and 20, add both of them and keep the sum back in array. Cost of this step would be (10+20) = 30.

• Now, A = [30,30,40], Cost = 30

• In the next step, we can remove 30 and 30. Add them and keep the sum back in array. Cost of this step would be (30+30) = 60.

• Now, A = [40,60], Cost = 60

• In the third step, we will remove  40 and 60 from the array and keep the sum back in array again. Cost of this step is (40+60) = 100.

• Now, A = [100], Cost = 100

So, the total cost turns out to be 190 (100+60+30).

Pseudo code for the above algorithm (when array is an sorted array)

sort(arr)

cost = 0

for(i=0; i<arr.length - 1; i++)

{

  arr[i+1] = arr[i] + arr[i+1]

  cost = cost +arr[i+1]

}