Hackerrank DP: Equal

Hello all, in this article, we’ll discuss the problem — Equal.

Problem Statement

Christy is interning at HackerRank. One day she has to distribute some chocolates to her colleagues. She is biased towards her friends and plans to give them more than the others. One of the program managers hears of this and tells her to make sure everyone gets the same number.

To make things difficult, she must equalize the number of chocolates in a series of operations. For each operation, she can give 1,2, or 5 pieces to all but one colleague. Everyone who gets a piece in a round receives the same number of pieces.

Given a starting distribution, calculate the minimum number of operations needed so that every colleague has the same number of pieces.

Input Format

The first line contains an integer t, the number of test cases.

Each test case has 2 lines.
- The first line contains an integer n, the number of colleagues, and the size of arr.
- The second line contains n space-separated integers, arr[i], the numbers of pieces of chocolate each colleague has at the start.

Constraints

1≤t≤100

1≤n≤10000

The number of chocolates each colleague has initially < 1000.

Sample Input

STDIN       Function
-----       --------
1           t = 1
4           arr[] size n = 4
2 2 3 7     arr =[2, 2, 3, 7]

Sample Output

2

Approaching the Problem

Let’s rephrase the problem here. “Given an array, you have to make all numbers of the array equal. You can only add 1,2 or 5 in each step to all but one element. In each step, you can add only one of the numbers. Finally, you have to return the minimum number of steps to make all elements equal.”

Now, here we have to answer a minimum result. Whenever we talk about minimum/maximum questions, I keep two approaches handy, greedy and dynamic programming. Things are different if it’s a graph problem.

Honestly, I couldn’t solve this question on the first attempt because it’s a tricky question, and I was stuck on solving it by recursion, but that didn’t work. The discussion forum was helpful in this case. It looks like a greedy approach can solve it, but we’ll need to rephrase it again.

The Real Approach

One can observe that adding to all but one element is technically the same as subtracting from that one left-out element. Let me elaborate:

Take an example of [2, 2, 3, 7]. The consecutive difference here is [0, 1, 4]. If I add 2 to all elements except 7, the array looks like this — [4,4,5,7], and the consecutive differences are — [0,1,2]. From the original array, if I subtract 2 from 7 only, the array becomes — [2,2,3,5], and consecutive differences are — [0,1,2]. You can see that the consecutive differences in both the cases are the same, which means both the operations are the same. Our goal is to make the consecutive difference array — [0,0,0].

Now, we can rephrase the question. “Given an array, you have to make all its elements equal. In one step, you can subtract 1, 2, or 5 from any element. Finally, calculate the minimum number of steps.”

What should be the baseline?

Now, we know that we need to make all the elements same but what should be the baseline? By baseline I mean till what value should we reduce the values so that they become equal eventually? Should we reduce it up to the minimum element? But that won’t be optimal. Let me give you an example.

arr = [0, 4, 4]

If we reduce it to the minimum element, the steps are:

1. Reduce 2 from 4 => [0, 2, 4]
2. Reduce 2 from 4 => [0, 2, 2]
3. Reduce 2 from 2 => [0, 0, 2]
4. Reduce 2 from 2 => [0, 0, 0]

However, the optimal steps should be:

1. Reduce 5 from 4 => [0, -1, 4]
2. Reduce 5 from 4=> [0, -1, -1]
3. Reduce 1 from 0 => [-1, -1, -1]

Another example can be arr = [0, 3, 3]

The optimal steps should be :

1. Reduce 5 from 3=> [0, -2, 3]
2. Reduce 5 from 3=> [0, -2, -2]
3. Reduce 2 from 0 => [-2, -2, -2]

The observation is that the baseline can be either the minimum element, minimum element-1, or minimum element-2. It is because you need two steps to reduce a 3 and same goes for 4. We can be better off subtracting 5 in some cases as we saw above.

We have got 3 baselines now. We try to reduce the elements to the 3 baselines and check which baseline has the minimum number of steps.

How to calculate the number of steps till the baseline greedily?

First calculate how much the element needs to be reduced. Let’s call this ‘dist’. Say the baseline is -2 and the element is 5. So the element needs to be reduced by dist = 5-(-2) = 7.

int dist = arr[i] - (min_elem-base);

Now, first reduce the dist by 5, then by 2, and then by 1. The result will be the number of steps for the given element. Do it for all baselines and all elements.

int steps = dist/5 + (dist%5)/2 + (dist%5)%2;

The complete c++ code will look like —

int equal(vector<int> arr){
  int ans = INT_MAX;
  int min_elem = *min_element(arr.begin(),arr.end());
  for(int base=0; base<3; base++){
    int temp = 0;
    for(int i=0;i<arr.size();i++){
       int dist = arr[i] - (min_elem - base);
       int steps = dist/5 + (dist%5)/2 + (dist%5)%2;
       temp+=steps;
    }
    ans = min(ans, temp);
  }
  return ans;
}

That’s it we’re done!

Hope this helped.