Social-Verifier's blog

Making All Elements of Array Equal
By Social-Verifier, history, 2 years 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

Comments Comments (7)
| Write comment?
»
2 years 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 :)

→ Reply
  • »
    »
    2 years 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

    → Reply
    • »
      »
      »
      2 years 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.

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

        Sorry for the dumb question but why not mean?

        → Reply
        • »
          »
          »
          »
          »
          2 years 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.

          → Reply
»
2 years 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.

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Question using this property Minimum Operations to Make a Uni-Value Grid

→ Reply