Skip to main content

Stick lengths

There are n sticks with some lengths. The task is to modify the sticks so that each stick has the same length. You can either lengthen or shorten each stick, both operations cost x, where x is the difference between new and original length.

What is the minimal total cost?

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
 import java.util.*;
 public class Stick{
     public static void main(String []args){
        int[] sticks = { 2, 3, 1, 5, 2 };
        //sort the array to find the median
        Arrays.sort(sticks);
        int med = sticks[sticks.length/2];  // median 
        int ans = 0;
        for(int i=0; i<sticks.length; i++)
            ans += Math.abs(sticks[i]-med); 
        System.out.println("Cost:"+ans);
     }
 }

Python


sticks = [ 2, 3, 1, 5, 2 ]
sticks.sort()
med = sticks[len(sticks)//2]
cost = 0
for stick in sticks:
    cost += abs(stick-med)
print("cost :",cost)