Reading time: 20 minutes | Coding time: 5 minutes

Given an array, find the minimum number of operations to make all the array elements equal. The operation includes incrementing all but one element of the array by 1 that is incrementing N-1 elements out of N elements.

In first example, we can get all elements to be equal in three operations in the following way:

1, 2, 3 → 2, 3, 3 → 3, 4, 3 → 4, 4, 4

This is a well-known problem. Let’s solve this once and for all!
Note that we need to find the minimum operations. What does that mean? Take the above case as an example, we could have done it the following way and thus in many other ways.

1, 2, 3 → 2, 2, 4 → 3, 2, 5 → 4, 3, 5 → 5, 4, 5 → 5, 5, 6 → 6, 6, 6

What ensures the minimum operations?

In order to make everything equal, first step would be that at least all the other elements should first try to be the same as the highest one, and in the process if some other element exceeds the highest, then also fine, it itself becomes the highest, and the other elements then try to be the new highest and so on until all elements become equal. This will make sure we are performing a minimum number of operations, because for all elements to be equal, at least they should all be the same as the current highest element in the array. We had not taken the highest as the bound in the above example, thus got 6 operations.

So the approach becomes pretty simple. Could you think of it? Take a few minutes...
Yeah, that’s correct. Take the current maximum one in the array, and increment all the other elements by 1 and update the current maximum. Go on doing this, until all elements become equal. The time complexity would be O(n^2).

But this was simple..

Could we do better?

Don’t go along the lines of the problem. Try to understand what it means to increment all except one element by one. Try to modify what you are doing right now in such a way that instead of working on n-1 elements each time, you work on just 1 element. Give a few minutes thinking about what I said.

=>1, 2, 3
* 2, 3, 3     (Increment all but highest element by 1)
* 1, 2, 2	    (Decrement the highest element by 1)

What’s our ultimate goal? To find the minimum number of operations required to make the elements equal, right? How does that matter if you make them equal to the highest one or the lowest one?

Here’s a quick analogy. You are a family of 5, and you stay at your college hostel. They want to meet you through the shortest path. All 4 of them can either come to you or just you go to them. The result is the same that you 5 met. So incrementing other elements by one keeping one same is similar to decrementing that one element by one. Okay?

So the operation becomes: Decrement an element by 1.

What should be the bound? For all elements to be equal, all of them should reach the minimum element.

By how much should we decrease 5 to reach minimum (1) : 4 operations (5-1)
For 3 : 2 operations(3-1)
For 2: 1 operation (2-1)
And for 1, no operation as it’s already minimum

And thus,

For every element A[i], the number of operations will be A[i] - minimumInArray
And the total minimum operations will be the sum of each element’s operations.

Algorithm

1. Find the minimum element in the array. This will be the target value which all the other elements will try to reach.
2. Initialize minimumOperations variable to 0.
3. For each element in the array A[i], find A[i]-min.
   This is the amount of decrement operations done for one element.
   Keep adding this value to the minimumOperations variable
4. Output the result as minimumOperations.

Implementation

Following is the code in java to this problem:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class EqualizeEveryone {
    public static void main(String[] args) throws java.lang.Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        while (t-- > 0){
            int n = Integer.parseInt(br.readLine());
            int[] arr = new int[n];
            String[] input = br.readLine().split(" ");
            int min = Integer.MAX_VALUE;
            for(int i=0; i<n; i++){
                arr[i] = Integer.parseInt(input[i]);
                min = Math.min(arr[i],min);
            }
            int minOperations = 0;
            for(int i=0; i<n; i++){
                minOperations += arr[i]-min;
            }
            System.out.println(minOperations);
        }

    }
}

One more observation:

Consider A1, A2, A3, A4 are elements of the array and min is the minimum
For every element Ai, number of operations will be Ai - min
Thus total operations become
(A1-min) + (A2-min) + (A3-min) + (A4-min)
= A1+A2+A3+A4 - 4 * min
= sumOfArrayElements - n * min
Where n is the size of array. So you could directly find the solution.

Complexity

Time complexity
O(n)
where n is the number of elements in the array
for finding sum and min

Space complexity
O(1)
We are not using any data structure to store anything.