Why does mean NOT work in CSES-Stick Lengths?

Here is the link to the problem:
https://cses.fi/problemset/task/1074

If you just want a counter example, consider the case 1,2,1005. Here it is optimal to take median value to be final length of sticks rather than taking mean.

1 Like

@lonely_coder12 i tried to do it using median but getting WA on last test case:

`n = int(input())
 b = 0
 arr = sorted(list(map(int, input().split())))
 z = len(arr) 
 med = int(arr[len(arr) // 2])
 for i in set(arr):
     b += abs(i - med)
 print(b)`

Corrected Code:

n = int(input())
b = 0
arr = sorted(list(map(int, input().split())))
z = len(arr) 
med = int(arr[len(arr) // 2])
for i in arr:
    b += abs(i - med)
print(b)

@anon58263146 You just need to remove that “set” from your code. It actually removes the duplicate elements, and that is wrong. The reason why your incorrect code worked on the sample test case provided with the problem statement is that the median itself is 2 in that case and |2-2| = 0, so even if you remove duplicate 2 's you still get the correct output.

Thanks, i didn’t notice that i used set… :sweat_smile:

mean works for the case when the cost is difference square

can someone pls tell the intuition behind the approach to this problem? I heard William lin saying “It’s a well-known problem”.

1 Like

Its a well known math problem. If you have a list of numbers and want to find the minimum cost to make them same , then you can achieve this by making them all equal to the median of the list.

This book explains it in a very easy to grasp manner.