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?
79 Answers
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]) # 40And 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.
0You 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.
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]));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)`
1PriorityQueue is an unbounded queue based on a priority heap and the elements of the priority queue are ordered by default in natural order.[1]
The head of the priority queue is the least element based on the natural ordering or comparator based ordering, if there are multiple objects with same ordering, then it can poll any one of them randomly. When we poll the queue, it returns the head object from the queue.[1]
So if we take an example where array arr[] = [5,5,5,5,5]
Here is how it will work:
Note: The below iteration is for demonstration purpose only. The PriorityQueue may not have same ordering but it makes sure to give the minimum element when it is polled
Queue : 5 5 5 5 5
Iteration 1 : 5 5 5 10 :- Cost: 10
Iteration 2 : 5 10 10 :- Cost: 10 + 10 = 20
Iteration 3 : 10 15 :- Cost: 20 + 15 = 35
Iteration 4 : 25 :- Cost: 35 + 25 = 60public static int min_cost(int[] arr)
{ PriorityQueue<Integer> queue = new PriorityQueue<>(); //adding all the elements to the queue for(Integer i : arr) { queue.offer(i); } int temp = 0; int cost = 0; while(queue.size() > 1) { // Removing the first two minimum elements from the queue int first = queue.poll(); int second = queue.poll(); temp = first + second; cost += temp; //Adding back the sum of the minimum elements back to the queue queue.offer(temp); } return cost;
}Reference: [1]
Here's my solution in java:
int cost = 0;
for (int i=1; i<Array.length; i++) { Array[i] += Array[i-1]; cost += Array[i];
}
return cost;#
# Complete the 'reductionCost' function below.
#
# The function is expected to return an INTEGER.
# The function accepts INTEGER_ARRAY num as parameter.
#
from bisect import insort
def makeReduction(num): first = num[0] second = num[1] cost = first+second del num[:2] insort(num,cost) return cost
def reductionCost(num): # Write your code here if len(num) <= 1: return 0 num.sort() totalCost = 0 while len(num) >= 2: totalCost += makeReduction(num) print(totalCost) len(num) return totalCostThere is a simple solution for this, I cant say it take the least time and memory but it will give correct solution.
def reduction(num):
cost = 0
while len(num) > 1: num.sort() first = num.pop(0) second = num.pop(0) cost += first + second num.append(cost)
return costSince the aim is to reduce the cost, we have to sort the array on each iteration.
function reductionCost(num) { let cost = 0; while (num.length > 2) { num.sort((a, b) => { return a - b; }); const newValue = num.shift() + num.shift(); cost += newValue; num.splice(num.length, 0, newValue); } return cost + num[0] + num[1];
}
console.log(reductionCost([1, 2, 3, 4]));
