Given an Array of N elements and we want to make all elements in array equal we can do 2 following operations
- increase any element by 1
- decrease any element by 1
What is the minimum number of operation we can do to make all elements in array equal. ?
I tried this problem and found that making every element equal to the median of array is optimal is there any proof for this. ?
Yes.
How much formal proof do you need?
The best proof that something is minimized is to calculate derivative. Derivative of |ai — x| is sign(ai — x). Sum of sign(ai — x) is equal zero when x is a median
QED :)
like i want to know why its optimal to make all elements equal to median and not any other value. like why dont we make every element equal to average of array
More intuitive approach then.
Let's have 5 random values:
1 4 5 9 10
Now. The median is 5. What happens when i move x to the right? My distance to 9 and 10 will be smaller, but my distance to 1, 4 and 5 will be larger. Each delta distance will be equal (9-5 to be exact), and because we add 3 times this value and subtract only 2 times, our final result will be larger.
Same if we move x to the left. Farther we move x, the worst is our result.
Sorry for the dumb question but why not mean?
Sure. So why mean is the first thing that we are thinking of? Because in school we learned that mean minimize some values. What values mean minimize? Well... Square error for example.
If you know derivatives you can easily compute that mean minimize square values and median minimize absolute values (as I show in first comment).
So if in your task is to choose x, such that sum_i (a_i — x)^2 will be minimal — you should use mean. If your task is to choose x, such that |a_i — x| will be minimal — you should use median.
I wanna ask something. Derivatives are defined for only continuous functions and here |ai — x| is clearly discontinuous since ai is defined only exactly at integral values of i. So I guess the derivatives proof is not mathematically correct or am I wrong.
Actually we calculate derivatives for x. And we can think about x as a real number. ai is constant in our case.
https://codeforces.com/problemset/problem/1520/E
Try this question, it has the same concept that you are trying to find, but it will give you visualization. If you are unable to think of the problem, do let me know I will tell you the idea which will help you in your problem as well.
Question using this property Minimum Operations to Make a Uni-Value Grid