The “Distribute Candies to People” problem is a classic coding interview question that challenges your understanding of array manipulation, mathematics, and iteration techniques. In this in-depth article, we will explore various ways to tackle this problem, from brute-force solutions to more optimized algorithms. Alongside, we’ll examine the time and space complexities of each approach.
Here’s the problem description as given on Leetcode:
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.
Input: candies = 7, num_people = 4 Output: [1,2,3,1]
A straightforward approach to solve this problem is to iterate through the people and distribute the candies one by one according to the pattern specified.
def distributeCandies(candies, num_people): result =  * num_people i = 0 candy_to_give = 1 while candies > 0: result[i % num_people] += min(candy_to_give, candies) candies -= candy_to_give candy_to_give += 1 i += 1 return result
The time complexity is O(n), where n is the total number of candies.
The space complexity is O(k), where k is the number of people, which is used for the result array.
By closely examining the problem, you’ll find that the series of candies given to each person forms an arithmetic series. We can solve this by finding out how many complete rounds of distribution can be made and then handling the remaining candies.
To find the number of complete rounds, we use the equation for the sum of the first n natural numbers,
where S is the total number of candies and n is the total number of complete rounds for one person.
def distributeCandies(candies, num_people): result =  * num_people # Calculate number of complete rounds n = int(((8 * candies + 1) ** 0.5 - 1) / 2) complete_rounds = n // num_people remaining = n % num_people for i in range(num_people): # Full rounds result[i] += (i + 1 + i + 1 + (complete_rounds - 1) * num_people) * complete_rounds // 2 # Remaining if i < remaining: result[i] += i + 1 + complete_rounds * num_people # Add the remaining candies result[remaining] += candies - n * (n + 1) // 2 return result
The time complexity is O(k), where k is the number of people.
The space complexity is O(k) for storing the result array.
itertools.cycle() provides a convenient way to iterate over the list in a cyclical fashion.
from itertools import cycle def distributeCandies(candies, num_people): result =  * num_people for i, c in zip(cycle(range(num_people)), range(1, candies + 1)): give = min(candies, c) result[i] += give candies -= give if candies == 0: break return result
The time complexity is O(n).
The space complexity is O(k).
The “Distribute Candies to People” problem provides an excellent exercise for understanding array manipulation and arithmetic sequences. While the brute-force approach is simple to implement, it lacks the performance that other optimized approaches offer.
The mathematical approach significantly improves the time complexity to O(k), making it the most optimized solution in terms of time complexity. On the other hand, using
itertools.cycle() allows for more Pythonic and readable code while maintaining decent performance.