SALARY: The Minimum Number Of Moves

SALARY: The Minimum Number Of Moves
Link for the problem: SALARY

Problem:
In the problem, there is an array where ith element denotes salary of the ith worker. Your task is to equalize all salary in minimum no of operations. In one operation we can select ith salary, and increasing every salary by 1 except the selected one. We can select different worker's salary in different operations.

Solution:

The problem can be solved by applying the greedy approach.
1) First sort the array in ascending order.
2) Now select the lowest element i.e. a[0] and make it equal to a[1]
   i.e. we are selecting a[1] in every operation until a[0] becomes equal to a[1]. Update other elements accordingly.
3) now select a[2] apply the operation until a[1] becomes equal to a[2]
  -> This will make a[0],a[1], and a[2] equal
4) Similarly doing this up to a[n-1]
5) counting the number of operation every time.

This is O(n2) approach. This problem can also be solved in O(n).

Code:
Below is the code with O(n) complexity:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int  t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        int a[n],i,j,k;
        for(i=0;i<n;i++)
        scanf("%d",&a[i]);
        sort(a,a+n);
        int p1=a[0],p2,c=0,s=0;
        for(i=1;i<n;i++)
        {
            s=s+(a[i]+c-a[i-1]);
            c=c+a[i]-a[i-1];
        }
        printf("%d\n",s);
    }
    return 0;
}