Distribute Candies to People Leetcode Solution

Table of Contents

Problem Statement

In this problem, we are given two numbers candies and num_people. The first number candies is the number of candies we have. num_people shows the number of person in which we have to distribute the candies.

The rule of candies distribution is:
We start from the leftmost person give him 1 candy then we give 2 candies to 2nd person, 3 candies to 3rd person till n candies to nth person. After that we again start from leftmost person giving him n+1 candies then n+2, n+3. This cyclic distribution continues till we run out of candies i.e. when our remaining candies will be less than current requirement, we will give the remaining candies to current person and then we stop.

Example

candies = 7, num_people = 4

[1,2,3,1]

Explanation:

On the first turn, ans[0] += 1, and the array is [1,0,0,0].
On the second turn, ans[1] += 2, and the array is [1,2,0,0].
Third turn, ans[2] += 3, and the array is [1,2,3,0].
Fourth turn, ans[3] += 1 (because there is only one candy left), and the final array is [1,2,3,1].

candies = 10, num_people = 3

[5,2,3]

Explanation:

On the first turn, ans[0] += 1, and the array is [1,0,0].
On the second turn, ans[1] += 2, and the array is [1,2,0].
Third turn, ans[2] += 3, and the array is [1,2,3].
Fourth turn, ans[0] += 4, and the final array is [5,2,3].

Approach 1 (Brute Force)

The simplest approach is to give l candy to first person and give 2 to 2nd person and so on move to last person. Then again start from first person giving him candies accordingly.
This can be done using a nested loop, in which the outer loop will run for the condition that is there any candy remaining or not. The inner loop will run from left to right which will sum up each position values with current candies to be given. But There may be a situation in which the currently remaining candies will be smaller than current requirement. Thus, there is an if else condition in inner loop.

when the currently required candies is greater than remaining candies, the remaining candies will be given to the current person. Otherwise, the current required candies will be given to the current person.

Implementation for Distribute Candies to People Leetcode Solution

C++ Program

#include <iostream>
#include <vector>
using namespace std;
vector<int> distributeCandies(int candies, int num_people) {
        vector<int>ans;
        /*
        initially everyone has no candy. Thus, answer array is filled up with zeros.
        */
        for(int i=0;i<num_people;i++){
            ans.push_back(0);
        }
        int cur=0;//current requirement is initialized to zero
        while(candies>0){
            for(int i=0;i<num_people;i++){
                cur++; //current requirement increments by one each time.
                if(candies>=cur){ //checks if the remaining candies are greater than current requirement 
                ans[i]+=cur;
                candies-=cur;
                }else{
                    ans[i]+=candies;
                    candies=0;
                }
            }
        }
        return ans;
    }
int main()
{
    int candies=10,num_people=3;
    vector<int>ans=distributeCandies(candies, num_people);
    for(int i:ans)cout<<(i)<<" ";
}

5 2 3

Java Program

import java.util.*;
import java.lang.*;

class Rextester
{  
    public static void main(String args[])
    {
        int candies=10, num_people=3;
        int[]ans=distributeCandies(candies, num_people);
        for(int i:ans)System.out.print(i+" ");
    }
    public static  int[] distributeCandies(int candies, int num_people) {
        int[]ans=new int[num_people];
        Arrays.fill(ans,0);
        int cur=0;
        while(candies>0){
            for(int i=0;i<num_people;i++){
                cur++;
                if(candies>=cur){
                ans[i]+=cur;
                candies-=cur;
                }else{
                    ans[i]+=candies;
                    candies=0;
                }
            }
        }
        return ans;
    }
}

5 2 3

Complexity Analysis for Distribute Candies to People Leetcode Solution

Time Complexity

O(max(sqrt(candies))): Current requirement increases by one in every loop. So, number of candies first decrease by 1 then decrease by 2 and so on.
So, after time t, the number of candies dropped is t*(t+1)/2 or about t^2 candies are dropped after time t.
Thus to drop c candies we need sqrt(c) time.
Thus, the time complexity is sqrt(candies).

Space Complexity

O(num_people): An array of size num_people is used. Thus, space complexity is O(num_people).

Approach 2 (Binary Search)

In previous approach, we were giving candies to each person one by one. Then, again we cyclically start giving candies from start. This is definitely a time consuming process.
So, In this approach, we will basically perform the following steps.

Firstly, we calculate the total number of complete fulfilment of candies. i.e. we will find out the total people who get exact candies according to rule.
The distribution starts from 1 and increments by 1. Thus the distribution must be something like, 1 2 3 4 5 6. Now suppose we have successfully given candies 6 times. Then the number of total candies consumed is sum of first 6 natural numbers.
Thus we can say that at any point of time, the number of candies consumed is sum of n natural numbers where n is the distribution done till that point of time.
Now we want the maximum successful distribution according to the rule. i.e. we want the max value of n such that n(n+1)/2 <= total number of candies.

For finding out the value of n, we have multiple approaches. We can solve the quadratic function for n or we can start for n=1 and keep substituting the value of n with incrementing value of n by 1 linearly. But the most appropriate solution is to use binary search here.

Binary search to find value of n.

To use binary search here, we must know the bound in which n can come. We can say that at least value of n can be 1 because, the constraint of candies is at least 1. So, we can at least give 1 candy to first person, so making one successful distribution (So, lower bound l=1). The upper bound of n can be complicated to calculate, so we are simply giving it a very large integer value by our self (let upper bound r=1000000).

Now we want a point n between l and r which is the max value which satisfies the equation.
n(n+1)/2 <= total number of candies.
If any point (let a point mid) between l and r satisfies the above equation. and the next point (i.e. mid+1) can’t satisfy the equation. Then mid will be the max number of successful distribution.

After we have found the number of successful fulfilments (mid), we can easily calculate number of complete cycles of distribution, which is k=mid/num_people.

Now we are calculating the candies to each person after k complete cycles.

Distribute Candies to People Leetcode Solution

So, we have found the mathematical terms to calculate the number of candies after k complete cycles. What about k+1 th incomplete cycle.
In k+1 th incomplete cycle, we can easily say that the successful fulfilment of candies will not go to nth people, our candies will be finished somewhere in between.

We have already calculate that our last successful fulfilment is mid. And mid%num_people person will be taking those mid th candies. And the next person will get all the candies remaining.

Distribute Candies to People Leetcode Solution
Thus we will add this last incomplete cycle distribution to our first mid%num_people and 1+mid%num_people will get all the remaining candies.