Minimum Moves to Equal All Array Elements

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

Example:

Input:
[4,2,4]

Output:
4

Explanation:
Only four moves are needed (remember each move increments two elements):
[4,2,4]  =>  [5,3,4]  =>  [5,4,5]  =>  [6,5,5]  =>  [6,6,6]

Approach: It is given in the problem that in every move we are going to increment n - 1 elements by 1. We can also think that in a way we decreasing that one remaining number by 1 so now the problem is in how many moves we can make every number in the array equal to the minimum number of the array. Given we are decrementing one number by 1 in each move, we can say that the number of moves will be:

Sum(nums[i] - Min(nums)) where i = 0 to n

So our algorithm would be: 

• min = Min(nums)
• result = 0;
• FOR i = 0 to n
• result = result + (nums[i] - min)
• RETURN result

Another solution is as follows:

Say the elements of the array nums are a0, a1, a2, a3,...,an and the Min(nums) is a0. As per the algorithm given above, our solution will be:

(a0 - a0) + (a1 - a0) + (a2 - a0) + ... + (an - a0)

= (a0 + a1 + a2 + ... + an) - (a0 + a0 + a0 +....n times)

= Sum of elements of nums - n * a0

= Sum(nums) - Length(nums) * Min(nums) 

Implementation in C#:

        public static int MinMoves(int[] nums)

        {

            int min = int.MaxValue, sum = 0;

            foreach(int num in nums)

            {

                sum += num;

                min = Math.Min(num, min);

            }

            return sum - min * nums.Length;

        }

Complexity: O(n)