So, you can find the minimum number of steps by this equation
int min = (sum of the array)-(minimum element*(size of the array);
and this equation gives AC!!
for ex
we have array
1 2 3
So, min = (6-(1*3) ==>3
Anybody know how this equation works?
Thanks in advance!!
steps for what?
Equation int min = (sum of the array)-(minimum element*(size of the array);
why and how this works
The mathematical derivation is easy.
Lemma: We have to equalize the salary, this means that difference between every worker’s salary must be 0.
What operation is available to us? To increase salary of every worker except 1.
Think it like this, what effect does it have on the relative difference?
The difference, of course, decreases by 1, but theres another observation to this.
Observation: Increasing salary of all workers except 1 has same result as decreasing that guy’s salary by 1 and keeping everyone’s salary as it is. We can mathematically prove that effect on difference of salaries is same (and hence on amount of operations to equalize), even though final salaries are different. [The answer is independent of final salary/absolute values. It depends on relative values, i.e. how is this array value in comparison with other array values]
So we transform operation to this-
“Chose a guy and decrease his salary by 1” , since in terms of operation needed to equalize salary, it will give same result.
Now it becomes simple. We just pick up the minimum element, and find operations needed to convert each element to minimum element.
Challenge: If you understood the concept, give a hand at this problem- https://www.hackerrank.com/challenges/equal/problem
Steps-
Arr=[1,2,3]
Minimum element=1.
1st element - arr[0]=1. Already minimum. Operations needed=0;
2nd element- arr[1]=2. To convert to minimum element, need 1 operation. Operations=1
3rd element- arr[2]=3, to convert to minimum element, need 2 operations. Operations=3
Q- Why the minimum element?
Because we showed that the transformation giving in question is equivalent to picking up a worker and reducing his salary by 1 (in terms of difference of salaries).
So, obviously this operation cannot increase any worker’s salary. So to equalize salaries, we need to reduce salaries of all workers till they are equal. The only possible option is to convert each to minimum element.
So, does that mean we need to find the max value of the array and decrease by 1? I’m sorry I’m confused
Let’s say we have 1 2 3 array can you show me each steps?
Wait what’s the middle element? “and find operations needed to convert each element to middle element.”
" We just pick up the minimum element, and find operations needed to convert each element to middle element." I’m confused about this statement
Why the minimum element?
Gimme a second. Damn typos! Minimum element. Sorry for types, its 2:20am and i am still studying for mid term exams XD
Thanks @vijju123 and thank you so much for providing me the same kind of problem for practice!! Thank you
You’re welcome dear 