Social-Verifier's blog

By Social-Verifier, history, 3 days ago, In English

Given an Array of N elements and we want to make all elements in array equal we can do 2 following operations

  1. increase any element by 1
  2. 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. ?

 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it

»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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 :)

  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      2 days ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

      • »
        »
        »
        »
        2 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Sorry for the dumb question but why not mean?

        • »
          »
          »
          »
          »
          2 days ago, # ^ |
          Rev. 2   Vote: I like it +1 Vote: I do not like it

          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.

»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Proof

For theoretical proof take a look at accepted answer and for mathematical proof have a look at 3rd or 5th answer.

»
2 days ago, # |
  Vote: I like it -8 Vote: I do not like it