Minimum Moves to Equal Array Elements II

Problem: Given a non-empty integer array, find the minimum number of moves required to make all array elements equal, where a move is incrementing a selected element by 1 or decrementing a selected element by 1.

Example:

Input:
[1,2,3,4]

Output:
4

Explanation:
Only two moves are needed (remember each move increments or decrements one element):

[1,2,3,4] => [2,2,3,4] => [2,2,2,4] => [2,2,2,3] => [2,2,2,2]

 

Approach: This is straight forward problem to solve. If you see the problem closely, you will notice that we want to make every element equals to the median of the elements in order to make minimum moves so we just take the sum of the differences of all the elements in the array and median. This sum is our answer. 

Implementation in C#:

    public int MinMoves2(int[] nums) 

    {

        int n = nums.Length;        

        Array.Sort(nums);        

        int median = n % 2 == 0 ? (nums[n/2 - 1] + nums[n/2]) / 2 : nums[n/2];        

        int moves = 0;        

        for (int i = 0; i < n; ++i)

        {

            moves += Math.Abs(nums[i] - median);

        }        

        return moves;

    }

Complexity: O(n)