We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Equal
  5. Discussions

Equal

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 422 Discussions, By:

votes

Please Login in order to post a comment

  • namdx1987
    7 years ago+ 36 comments

    I think we don't need to use dynamic programming here. First of all, if you give chocolate bars to all but chosen one, it is equivalent to take away the chocolate bar(s) from each chosen one until every one is equal. So the challenge becomes decrease from each individual 1, 2 or 5 until all are equal. Second to calculate the ops we need to use to decrease an integer n until it reaches 0 (call it the function f) is equivalent to convert 1, 5 (no need to use dynamic programming here). Finally, to solve this challenge, we find the min (call it m) of the given list, then for i from 0 to 4, we find min of ops[i]=sum(f(c-min+i)) where c is each individual colleague and thus no need to use dynamic programming here :)

    176|
    Permalink
    View more Comments..
  • liam_meck
    5 years ago+ 4 comments

    SPOILER! Hint if you're stuck:

    Giving chocolate to everyone except the chosen person is the same as taking chocolate away from the chosen person. We don't care about how much chocolate they end up with, only that each person's amount is equal.

    For example:

    Give 5:
     1  3  5
     6  8  5  <-
    
    Take 5:
     1  3  5
     1  3  0  <-
    
     The two results are the same relative to themselves, just shifted:
    
       1  3  0
     + 5  5  5
     ---------
       6  8  5
    

    The problem becomes much simpler now.

    Also remember to look for caching opportunities.

    31|
    Permalink
    View more Comments..
  • lovealmgren
    5 years ago+ 10 comments

    100% correct Java 8 Solution

    import java.io.; import java.util.;

    public class Solution {

    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;
    }
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        while(n-->0) {
            int m = in.nextInt();
            int cookies[] = new int[m];
            for(int cookie_i=0; cookie_i < m; cookie_i++){
                cookies[cookie_i] = in.nextInt();
            }
            System.out.println(find_min_actions(cookies));
        }
    
    
    }
    

    }

    30|
    Permalink
    View more Comments..
  • code_report
    4 years ago+ 0 comments

    Video solution with explanation: https://youtu.be/rdlzz2GOcq4

    11|
    Permalink
  • todd24
    4 years ago+ 2 comments

    Why does the problem say 3 chocolates when all of the discussions and editorial use 2?

    11|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature