Distribute Candies to People

Easy

Asked by:

10 views

Topics:

Arrays

We distribute some number of candies, to a row of n = num_people people in the following way:

We then give 1 candy to the first person, 2 candies to the second person, and so on until we give n candies to the last person.

Then, we go back to the start of the row, giving n + 1 candies to the first person, n + 2 candies to the second person, and so on until we give 2 * n candies to the last person.

This process repeats (with us giving one more candy each time, and moving to the start of the row after we reach the end) until we run out of candies. The last person will receive all of our remaining candies (not necessarily one more than the previous gift).

Return an array (of length num_people and sum candies) that represents the final distribution of candies.

Example 1:

Input: candies = 7, num_people = 4
Output: [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].
On the third turn, ans[2] += 3, and the array is [1,2,3,0].
On the fourth turn, ans[3] += 1 (because there is only one candy left), and the final array is [1,2,3,1].

Example 2:

Input: candies = 10, num_people = 3
Output: [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].
On the third turn, ans[2] += 3, and the array is [1,2,3].
On the fourth turn, ans[0] += 4, and the final array is [5,2,3].

Constraints:

1 <= candies <= 10^9
1 <= num_people <= 1000

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the number of candies and the number of people? Can either be zero?
Can `candies` or `num_people` be negative?
If the number of candies is not perfectly divisible and there are candies left over after distributing to all people, what should the last person receive?
Are we expected to return an array with the same length as the initial number of people?
If the number of candies is less than the amount needed to give the first person 1 candy, what should be returned?

Brute Force Solution

Approach

Imagine giving out candies to people in a line one by one. The brute force way means we simply keep giving out candies in a specific pattern until we run out of candies to give. We start over each time until all the candies are gone.

Here's how the algorithm would work step-by-step:

Begin by giving one candy to the first person.
Then give two candies to the next person, then three to the next, and so on.
If we run out of candies, stop and see if we've given all of them away.
If not, start over, giving the next person one more candy than before.
Keep doing this, distributing candies in increasing amounts to each person in the line, and then starting back at the beginning.
Repeat the entire process, until all the candies have been distributed.

Code Implementation

def distribute_candies(candies, number_of_people):
    distributed_candies = [0] * number_of_people
    candy_to_give = 1
    person_index = 0

    while candies > 0:
        # If we can give the current amount, give it
        if candies >= candy_to_give:
            distributed_candies[person_index] += candy_to_give
            candies -= candy_to_give
            candy_to_give += 1

        # If we can't give the current amount, give the remainder
        else:
            distributed_candies[person_index] += candies
            candies = 0

        # Move to the next person or start over if needed
        person_index += 1
        if person_index == number_of_people:
            # Reset the index to the beginning of the line.
            person_index = 0

    return distributed_candies

Big(O) Analysis

Time Complexity

O(sqrt(candies)) – The primary driver of the algorithm's time complexity is the distribution of candies until all candies are given away. The number of complete cycles through the people array and the last incomplete cycle contribute to the runtime. The number of candies given out increases linearly with each person receiving candies, making the total number of candies distributed related to the square of the number of distributions. Since we are essentially summing an arithmetic series (1 + 2 + 3...), the number of times we iterate through the people array is proportional to the square root of the total number of candies. Thus the time complexity is O(sqrt(candies)).

Space Complexity

O(1) – The algorithm uses a fixed-size array of size 'num_people' to store the number of candies each person receives. The length of this array depends on the input 'num_people', which we will consider a constant, since it doesn't affect the growth of the algorithm relative to the number of candies. The algorithm only uses a few integer variables to keep track of the current person and the number of candies to give, irrespective of how many candies are given. Therefore, the auxiliary space required remains constant regardless of the number of candies to distribute, resulting in O(1) space complexity.

Optimal Solution

Approach

We need to distribute a certain number of candies to people standing in a line, where we give candies one-by-one in increasing amounts until we run out, then we loop back to the start. The key idea is to figure out how many full cycles we can complete and then handle the remaining candies efficiently.

Here's how the algorithm would work step-by-step:

Figure out how many complete rounds of giving candies we can make to all the people.
Calculate the total number of candies given out during those complete rounds.
Subtract the candies used in complete rounds from the total candies available to determine how many candies remain for the incomplete round.
Give candies to each person again, starting from the beginning, until we run out of the remaining candies.
Add the candies from both the full rounds and the last, incomplete round, to figure out the total amount of candies each person receives.
The remaining candies, if any, will stop at the last person who can take the remaining candies.

Code Implementation

def distribute_candies(candies, number_of_people):
    distributed_candies = [0] * number_of_people
    candies_given = 0
    person_index = 0
    candy_to_give = 1

    # Continue distributing until we run out of candies
    while candies > 0:
        # If we have enough candies, give the current amount
        if candies >= candy_to_give:
            distributed_candies[person_index] += candy_to_give
            candies -= candy_to_give
            candies_given += candy_to_give
            candy_to_give += 1
        # Otherwise, give the remaining candies
        else:
            distributed_candies[person_index] += candies
            candies_given += candies
            candies = 0

        person_index = (person_index + 1) % number_of_people

    return distributed_candies

Big(O) Analysis

Time Complexity

O(sqrt(candies) + num_people) – The algorithm involves determining the number of complete rounds, which is related to the square root of the total candies because the sum of candies distributed in each round increases linearly. Thus, calculating the number of complete rounds takes O(sqrt(candies)) time. The remaining incomplete round iterates through the people array at most once, taking O(num_people) time. Therefore, the overall time complexity is O(sqrt(candies) + num_people).

Space Complexity

O(N) – The algorithm initializes an array of size N, where N is the number of people, to store the number of candies each person receives. The remaining calculations are done using variables that occupy constant space. Therefore, the dominant factor in space complexity is the array of size N, resulting in O(N) auxiliary space.

Edge Cases

Case	How to Handle
candies is zero	Return an array of size n filled with zeros immediately.
num_people is zero	Return an empty array, or throw an IllegalArgumentException as the problem is not well defined.
candies is a very large number	Use long data type for calculations to prevent integer overflow when calculating how many candies a person receives.
num_people is a very large number	The solution may become less efficient due to the large number of iterations, but it will still produce correct results within the constraints.
candies is slightly less than needed to complete a full distribution cycle	The last person receives the remaining candies which may be less than the amount for that round.
candies is just enough to complete a full distribution cycle	Each person gets the candies due for their position in the cycles, and candies will be zero at the end.
candies is negative	Throw an IllegalArgumentException or return an error status as the problem states we need to distribute candies.
A person receives a negative number of candies at some point during the distribution	Due to the nature of the algorithm, a person can't receive negative number of candies, but add a check for it anyway to handle unexpected behaviour, or the edge case above.

candies is zero

How to Handle:

Return an array of size n filled with zeros immediately.

num_people is zero

How to Handle:

Return an empty array, or throw an IllegalArgumentException as the problem is not well defined.

candies is a very large number

How to Handle:

Use long data type for calculations to prevent integer overflow when calculating how many candies a person receives.

num_people is a very large number

How to Handle:

The solution may become less efficient due to the large number of iterations, but it will still produce correct results within the constraints.

candies is slightly less than needed to complete a full distribution cycle

How to Handle:

The last person receives the remaining candies which may be less than the amount for that round.

candies is just enough to complete a full distribution cycle

How to Handle:

Each person gets the candies due for their position in the cycles, and candies will be zero at the end.

candies is negative

How to Handle:

Throw an IllegalArgumentException or return an error status as the problem states we need to *distribute* candies.

A person receives a negative number of candies at some point during the distribution

How to Handle:

Due to the nature of the algorithm, a person can't receive negative number of candies, but add a check for it anyway to handle unexpected behaviour, or the edge case above.