Algorithms - Dynamic Programming - Equal

Came across HackerRank last week and tried few coding challenges, and found this interesting practice for Dynamic Programming.
Equal - HackerRank and my submission


The challenge:

Christy is interning at HackerRank. One day she has to distribute some chocolates to her colleagues. She is biased towards her friends and may have distributed the chocolates unequally. One of the program managers gets to know this and orders 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.

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

Calculate minimum number of such operations needed to ensure that every colleague has the same number of chocolates.

Input Format

First line contains an integer denoting the number of testcases. testcases follow.
Each testcase has lines. First line of each testcase contains an integer denoting the number of co-interns. Second line contains N space separated integers denoting the current number of chocolates each colleague has.

Output Format

lines, each containing the minimum number of operations needed to make sure all colleagues have the same number of chocolates.

Constraints

1 <= T <= 100  
1 <= N <= 1000  

Number of initial chocolates each colleague has < 1000

Sample Input

1  
4  
2 2 3 7  

Sample Output

2  

Explanation

1st operation: Christy increases all elements by 1 except 3rd one  
2 2 3 7 -> 3 3 3 8  
2nd operation: Christy increases all element by 5 except last one  
3 3 3 8 -> 8 8 8 8  

Analyze:

First of all why use Dynamic Programming?
The problem looks like add chocolates to everyone expect one person until equal. However, if think the other way around it's all about minimise the different between the max and min number in the array. Also add to all but one really equals to just take same number from one, for example give everyone 2 chocolates except one, to the perspective of minimise the difference, it's same as take 2 chocolates from the one who doesn't add 2.
Thus, the question can be rephrase to each time Christy can take 1, 2 or 5 chocolates form a chosen person until all equal.


Code:

JAVA in O(T * N * 3)

Submission on HackerRank

import java.io.*;  
import java.util.*;  
import java.text.*;  
import java.math.*;  
import java.util.regex.*;

public class Solution {  
    static boolean DBG = false;

    // Min number in the Array.
    static int min;

    //Find the minimised action counts 
    static int MinRound(int[] counts){

        int[][] results = new int[counts.length][3];
        for (int i = 0; i< counts.length; i++){
            for (int j = 0; j<3; j++){

                //Determine baselines -- difference between possible Max and Min
                //Not only possible to take from Max values also can take from Min values
                //Like the case  1 5 5  -> 0 5 5 -> 0 0 5 -> 0 0 0
                //Baseline can be keep min, take 1 or 2 from min. 
                //Dont need to consider the case of take 5 coz it will not affect greedy approach below

                int delta = counts[i] - min +j;
                results[i][j] = 0;
                while(true){
                    // Greedy approach
                    if( delta >=5 ){
                        delta -= 5;
                        results[i][j]++;
                    }else if(delta >=2){
                        delta -= 2;
                        results[i][j]++;
                    }else if (delta >= 1){
                        delta -= 1;
                        results[i][j]++;
                    } else {
                        break;
                    }
                }
            } 
        }
        int finalResult = -1;
        // Compare results from different baseline cases (keep min, take 1, 2 ). 
        for (int i = 0; i< 3; i++){
            int subFinal = 0;
            for (int j =  0; j < counts.length; j++){
                subFinal += results[j][i];
                if(DBG) System.out.format("results[%d][%d] = %d \n",j,i,results[j][i]);
            }
            if(DBG) System.out.println(subFinal);
            if(finalResult < 0 || finalResult > subFinal){ finalResult = subFinal;}
        }

        return finalResult;
    }

    public static void main(String[] args) {

        int casesCount = 0;

        Scanner s = new Scanner(System.in);

         if(s.hasNextInt()){
        casesCount = s.nextInt();
         }
        s.nextLine(); // throw away the newline.

        int[] outputArrary = new int[casesCount];

        for(int i = 0; i < casesCount; i++){
            int count = 0;
            if(s.hasNextInt()){
                count = s.nextInt();
            }
            s.nextLine();

            int[] numbers = new int[count];
            min = -1;
            for (int j = 0; j < count; j++){
                if (s.hasNextInt()) {
                    numbers[j] = s.nextInt();
                    // get min value from input array
                     if (numbers[j] < min || min < 0){
                        min = numbers[j];
                     }
                } else {
                    System.out.println("You didn't provide enough numbers");
                    break;
                }
            }
            //SortCounts(numbers);
            outputArrary[i] = MinRound(numbers); 

        }

        for(int i = 0; i < casesCount; i++){
            System.out.println(outputArrary[i]);          
        }
    }
}
comments powered by Disqus