Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

Reading time: 20 minutes | Coding time: 10 minutes

Given n candy boxes, each box contains different number of candies. We need to distribute the candies amongst k friends such that:

All friends get equal number of candies
All the candies which a particular friend gets must be from a single box only.

Solving this problem will require concepts of Binary Search. This will take O(N * logM) time complexity where there are N boxes and M is the maximum number of candies in a box.

Find the maximum number of candies that can be distributed.

Number of candies in each box: 3, 1, 4
Number of friends: 2
Output: 3
Explanation: For 2 friends, 3 is the maximum number. We cannot have 4, because 3 and 1 are in different boxes and each person can get candies from one box only so we took
Number of candies in each box: 3, 2, 3, 9
Number of friends: 1
Output: 9

Here, I need you to note one thing.
More than one person can get the candies from the same box i.e. if there are 4 candies in the box, it’s possible that 2 persons take 2 candies each. Here’s a test case that can explain it:
k = 4
2, 4, 1, 3, 1
We can distribute maximum 2 candies to each person. Here box with 4 candies is used two times.
Alright, let’s see how we can do it.

What’s the maximum candies you can distribute to each person?

The sum of all the candies in the array? No!!!
Because remember, the candies given to a person can be from the same box only. So the maximum candies you can distribute to each person is the maximum element from the array. You cannot go beyond that. And since we have non zero candies in the box, the minimum we can give is 1. So, to any person, you can give candies ranging from 1 to max.

You can do one thing, starting from 1 to max, try to find if you can serve all the k people. Following example will make it clear:

In the case of 2, 4, 1, 3, 1
K = 4 people,
Max = 4,
We can distribute either 1, 2, 3, or 4 candies to each person.

If I decide to distribute 1 candy to each person,
Total people I can serve is : 2/1 + 4/1 + 1/1 + 3/1 + 1/1 = 11 and 11>k (4). Thus I can give 1 candy.
We did sum(arr[i] / candyToEach) to find the number of people who can get candies. Why? You think about it by yourself before moving on.

It’s simple. 10 candies in a box, I can give 2 to each. How many people I can serve to the max? 10/2 = 5. If there are n boxes, I will find out how many people I can serve with each box, and sum it over n to find the total number of people that I can serve. Going back to the example…

If I decide to distribute 2 candies to each person.
Total people I can serve is: 2/2 + 4/2 + ½ + 3/2 + ½ = 4 and 4==k. Thus I can give 2 candies to each person as well.
If I decide to distribute 3 candies to each person.
Total people I can serve is : ⅔ + 4/3 + ⅓ + 3/3 + ⅓ = 2. I can only serve 2 people which I cannot do.

Since 3 candies cannot fill 4 people equally with given conditions, even 4 candies won’t. Thus the answer is 2 candies.
We are done then, right? We find the max in the array. Starting from 1 to max, we start distributing the candies and find the number of people we can serve. Once that number is less than k we stop.

Could you optimize it?

Optimization

Here’s a hint: let z is the max in the candy box

We are checking the distribution of candies from 1 to z.

If you can give z/2 candies to k or more people, is there a need to check for the number of candies between 1 to z/2? No! Because you have to distribute the maximum amount. You would definitely have to check for candies between z/2 to z.
If you cannot give z/2 candies to k people, you won’t increase the amount of distribution, as that will lead to less than k people. Thus you will decrease your bound and search for a number between 1 to z/2.

What comes to your mind??

Binary search it is! And this way, we solved the given problem.
Read about binary search

This was an interesting problem. I would encourage you to understand it clearly and code it by yourself.

Algorithm

1. Find the maximum in the candy box array (to find
the upper bound for binary search).
2. Apply binary search with
low = 1
high = max
3. 
    a. If we can distribute candies with mid as the value 
of candies given to each person, we set low to be mid+1 
and result to be mid, i.e our search space shifts to the 
right side
    b. Else high = mid-1, i.e our search space shifts to left side.
4. Output the result.

Implementation

Following is the code in java to this problem:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class CandyDistribution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	//testcases
        int t = Integer.parseInt(br.readLine());
        while (t-- > 0){
            String[] input = br.readLine().split(" ");
            //n: number of candy boxes
            int n = Integer.parseInt(input[0]);
            //k: number of friends
            long k = Long.parseLong(input[1]);
            String[] input1 = br.readLine().split(" ");
            long[] arr = new long[n];
            long max = Integer.MIN_VALUE;
            for(int i=0; i<n; i++){
                arr[i] = Long.parseLong(input1[i]);
//we need to find max for the upper bound in the binary search.
                max = Math.max(max,arr[i]);
            }
            System.out.println(binarySearch(n, k, arr, max));
        }
    }
  public static long binarySearch(int n, long k, long[] arr, long max){
        long low = 1;
        long high = max;
        long mid;
        long res = 0;

        while (high>=low){
            mid = low + (high-low)/2;
            if(canDistribute(mid, n, k, arr)){
                low = mid+1;
                res = mid;
            }
            else{
                high = mid-1;
            }
        }
        return res;
    }
    
  public static boolean canDistribute(long val, int n, long k, long[] arr){
        if(k==1){
            return true;
        }
        long peopleServed = 0;
        for (int i=n-1; i>=0; i--){
//this is the number of people who can get candy
            peopleServed += arr[i]/val;
        }
        if(peopleServed>=k){
            return true;
        }
        return false;
    }
}

Complexity

Time complexity
O(log(max)*n)

where n is the number of candy boxes and max is the maximum in the candy box array. log is an optimization because of binary search

Space complexity
O(1)
We are not using any data structure to store anything.