Chocolate Distribution Problem

Chaitra Rai

·

Follow

2 min read

·

Oct 24, 2021

--

Listen

Share

Given an array of positive integers of size n, where each value represents the number of chocolates in a packet. Each packet can have a variable number of chocolates. There are m students, the task is to distribute chocolate packets among m students (Full Question) Another variant of this question is to distribute the chocolates such that the student with highest mark always gets a chocolate more than students adjacent to them(Question variant)

• Each student gets should get exactly one packet
• The difference between a maximum number of chocolates given to a student and a minimum number of chocolates given to a student is minimum
• to have the least difference the number of chocolates has to be sorted
• this way the distance between the numbers are less

public long findMinDiff (ArrayList<Long> a, long n, long m)
{
    long min_diff=Long.MAX_VALUE;
    long diff=0;
    if(n==0 || m==0)
        return 0;
    if(n<m)
        return -1;
    Collections.sort(a);
    for(int i=0;i+(int)m-1<n;i++){
        diff=a.get(i+(int)m-1)-a.get(i);
        if(diff<min_diff)
            min_diff=diff;
    }
    return min_diff;
}

• The time complexity of this solution is O(n)
• The other question focuses on distribution based on the marks/ rating a particular student has obtained
• We can maintain a temporary array to distribute the chocolates one by one based on the rating here; the minimum chocolate per student being 1
• We iterate from left to right and then right to left to check the difference between the adjacent values and increase the number of chocolates if the ratings are higher than the previous or next student

public int candy(int[] ratings) {
    int n= ratings.length;
    int[] temp=new int[n];
    for(int i=0;i<n;i++){
        temp[i]=1;
    }
    for(int i=1;i<n;i++){
        if(ratings[i]>ratings[i-1]){
            temp[i]=temp[i-1]+1;
        }
        else{
            temp[i]=1;
        }
    }
    for(int i=n-2;i>=0;i--){
        if(ratings[i]>ratings[i+1]){
            temp[i]=Math.max(temp[i],temp[i+1]+1);
        }
        else{
            temp[i]=Math.max(temp[i],1);
        }
    }
    int sum=0;
    for(int i=0;i<n;i++)
        sum+=temp[i];
    return sum;
}

• The time complexity of this algorithm is O(n) and it takes n extra space