Distribute Candies to People

January 19, 2024

Problem #

You have n candies, and you want to distribute them to a group of people arranged in a circle in the following way:

• Start at the first person (index 0), and then move to the next on the right for each distribution.
• In the first round, give 1 candy to the first person, 2 candies to the next person, and so on, until you run out of candies.

Find the final distribution of candies for each person.

Example:

1. Input: candies = 10 Output: [1, 2, 3, 4] Explanation: The first person gets 1 candy, the second person gets 2 candies, the third person gets 3 candies, and the fourth person gets 4 candies.

Solution Approach #

The solution involves simulating the distribution process, iterating over the people and distributing candies until they run out.

Algorithm Steps #

1. Initialize an array to store the distribution of candies.
2. Start with the first person and distribute 1 candy, then move to the next person with an incrementing number of candies.
3. Continue this process, wrapping around to the first person if necessary, until all candies are distributed.
4. Return the distribution array.

Code (Python) #

def distributeCandies(candies):
    distribution = [0] * candies
    i = 0
    while candies > 0:
        distribution[i % len(distribution)] += min(candies, i + 1)
        candies -= i + 1
        i += 1
    return distribution

# Test the function
print(distributeCandies(10))  # Output: [1, 2, 3, 4]

Time Complexity #

O(sqrt(n)), where n is the number of candies. The time complexity is determined by the number of rounds required to distribute all candies.

Space Complexity #

O(n), for the array storing the distribution of candies.