Hi,
This is the editorial for the SALARY problem mentioned in practice section under the DSA fundamentals certification.
Here is the link to the problem:
Here is the link to youtube video explaining the algorithm and solution to SALARY problem:
Here is the short description of algorithm:
After reading all the numbers, let us arrange them in ascending order:
x1 x2 x3 x4 . . . xn
x1 <= x2 <= x3 <= x4 . . . <= xn
Following are the broad steps to make all the numbers same:
In first step, first two numbers are made equal.
In second step, first three numbers are made equal.
…and so on till all the numbers become equal…
- Select x2 and increase all other numbers till x1 becomes equal to x2.
So (x2-x1) is added to all the numbers except x2.
After this step, the numbers become:
(x1 + x2 - x1) x2 (x3 + x2 - x1) (x4 + x2 - x1) . . . (xn + x2 - x1)
=
x2 x2 (x3 + x2 - x1) (x4 + x2 - x1) . . . (xn + x2 - x1)
- Select (x3 + (x2-x1) ) and increase all other numbers till x2 becomes equal to (x3 + x2 - x1).
So the amount to be added is equal to (x3 + x2 - x1) - x2 = (x3 – x1)
After this step, the numbers become:
(x2+ x3-x1) (x2+x3-x1) (x3+x2-x1) (x4+x2-x1+x3-x1) . . . (xn+x2-x1+x3-x1)
=
(x2+ x3-x1) (x2+x3-x1) (x3+x2-x1) (x4+x2+x3-2x1) . . . (xn+x2+x3-2x1)
- Select (x4+x2+x3-2x1) and increase all other numbers till (x2+ x3-x1) becomes equal to (x4+x2+x3-2x1).
So the amount to be added is equal to (x4+x2+x3-2*x1) - (x2+ x3-x1) = x4 – x1
So based on mathematical induction, at every step, the amount to be added is equal to (xi-x1) where i = 2 to n
So the total amount to be added is (x2-x1) + (x3-x1) + (x4-x1) + . . . + (xn-x1)
= x2+x3+x4+. . . +xn – (n-1)x1
= x1+x2+x3+x4+. . . +xn – nx1
= Σx – n*x1
Note that x1 is the minimum value in the entire list of numbers.
For the sake of understanding, we arranged the numbers in ascending order. But for solving this problem, we need not actually sort the numbers. All we need is sum of all the numbers and minimum value.