Equal hackerrank Solution

Equal hackerrank Solution

  September 01, 2017    

---

Problem :

Christy to make sure everyone gets equal number of chocolates.

But to make things difficult for the intern, she is ordered to equalize the number of chocolates for every colleague in the following manner,

For every operation, she can choose one of her colleagues and can do one of the three things.

She can give one chocolate to every colleague other than chosen one.
She can give two chocolates to every colleague other than chosen one.
She can give five chocolates to every colleague other than chosen one.

Explanation:

Here first we will sort the Array so that we can easily get the difference.
Find the difference for every element and modify that element by subtracting 5/2/1.
So we will first go with 5 then check with the remainder and follow same for 2,1.

Here base 0 to 2 is added because sometimes it is not necessary that we will get result from above algo as if diff is 4 then it better to add 1 then subtract 5.


But why base only till 0,1,2 and not more than 2?
if the diffence between x and y is: 
a)4 adding 1 is div by 5 
b)3 adding 2 is div by 5 
c)2 it is div by 2 
d)7 is div by 5 followed by 2 
e)8 adding 2 is div by 5 followed by 2 
f)9 adding 1 is div by 5 followed by 2 
Did you observe the base is cycling around 0,1,2.so you never need not go beyond 2

Code:

 public static long find_min_actions(int[] cookies) {

    Arrays.sort(cookies);

    long sum = Long.MAX_VALUE;

    for(int base = 0; base < 3; base++) {
        int current_sum = 0;
        for(int i = 0; i < cookies.length; i++) {
            int delta = cookies[i] - cookies[0] + base;
            current_sum += (int)delta / 5 + delta % 5 / 2 + delta % 5 % 2 / 1;
        }
        sum = Math.min(current_sum,sum);
    }

    return sum;
}