Minimum Candy Distribution – Interview Algorithm Problem

Recently in an online test I faced this question i.e. on how to minimize the number of candies/toffee to be distributed by a teacher and found that a lot of similar questions are frequently asked in a lot of interviews.

Read More – Possible beautiful arrangements

So the problem statement is –
A teacher has some students in class. She has to distribute some candies to these students. Every student has some grades/rank that he/she has acquired over a series of tests. Now students are sitting in a line in a random order(will be provided in input) and there are few rules that teacher has to follow while distributing the candies.

Rules are –

• Among any two students who sit adjacent to each other and have different grades, student with the higher grades must get extra candies.
• At least one candy is given to every student.
• Students sitting adjacent to each other and have same grades then there is no condition on the number of candies they get i.e. if one get 5 candies other can get 15 or even 1 or 5 or any other positive number(but we have to minimize this).

There might be other conditions on the input but for now, we will focus on the logic on how to do this –

The approach that I actually used in the test was different than the solution that I will be sharing today as it was the more complicated one and required some extra operations as well but it worked for me. So in a brief what I did was that I kept the last location upto which I need to increase the candies distributed in case there is a long chain of students sitting with decreasing order of grades.

For example – If there are 7 students and their grades are 2, 3, 4, 4, 3, 2, 1

If there are 7 students and their grades are 2, 3, 4, 4, 3, 2, 1

Then distribution is like-

After step 1,2,3 quantities distributed are– 1, 2, 3, 0, 0, 0, 0 (at this time 3rd student is marked as the last location upto which candy counter increment is needed because if we have to increase the number of candies of 3rd we need not worry about 2nd student because condition of higher candy does not breaks.)
After 4th step – 1, 2, 3, 1, 0, 0, 0 (because 3rd and 4th student have the same grade and we have to minimize the toffee, now 4th student is marked)
5th Step – 1, 2, 3, 2, 1, 0, 0 (increase count till marked because we have to give at least one candy to every student and also maintain another condition of students with different grades, still 4th is marked)
6th step – 1, 2, 3, 3, 2, 1, 0 (still 4th is marked)
7th step – 1, 2, 3, 4, 3, 2, 1

So this was the solution that I try. You can also try this by yourself but now let’s jump to a better solution and this will solve this problem in O(2n) time complexity and is much easier to implement and understand.

Theoretically in this approach first we go left to right and set “next” candy value to either “previous+1” or “1”. This way we get the up trends i.e. checking condition as per next student and not as the previous student sitting adjacently. Then we go right to left and do the same, this way getting the down trends.

Implementation of Candy problem

So lets suppose the input format is

• First line – A value for number of students (n)
• Next n lines – Grade of student.

import java.util.Scanner;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int arr[] = new int[n];

        for(int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }

        int candies[] = new int[n];
        candies[0] = 1;

        // First loop for up trends
        for(int i = 1; i<n; i++) {
            if(candies[i] == 0) {
                candies[i]=1;
            }

            if(arr[i] > arr[i-1]) {
                candies[i] = candies[i-1]+1;
            }
        }

        // Second loop for down trends
        for(int i = n-1; i > 0; i--) {
            if(arr[i-1] > arr[i] && candies[i-1] <= candies[i]) {
                candies[i-1] = candies[i]+1;
            }
        }

        // Calculating the sum - This step can be avoided by
        // addition and substraction in previous loops, but for
        // simplicity it is seperated out.
        long sum = 0l;
        for(int i = 0; i < n; i++) {
            sum += candies[i];
        }

        System.out.println("Minumum number of candies required to distribute are - "+sum);
    }
}

Input:-
8  
1  
2  
2
3
4
3
2
1

Output:-
Minumum number of candies required to distribute are - 16

So that’s all for this tutorial. Hope this helps and you like the tutorial. Do ask for any queries in the comment box and provide your valuable feedback. Do come back for more because learning paves way for a better understanding.

Keep Coding!! Happy Coding!! 🙂

Recommended -