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:
Problem Overview: You are given candies and num_people. Candies are distributed sequentially: the first person gets 1, the second gets 2, the third gets 3, and so on. Once the end of the row is reached, the distribution continues from the beginning until all candies are used. The task is to return an array showing how many candies each person receives.
Approach 1: Iterative Distribution (Simulation) (Time: O(√candies), Space: O(n))
This approach directly simulates the candy distribution process. Start with a counter representing how many candies should be given next. Iterate through people using index % num_people so the distribution wraps around in a circular manner. At each step, give min(remaining_candies, next_give) to the current person, subtract from the remaining total, and increment the give counter.
The key idea is straightforward simulation. The sequence of distributed candies follows 1, 2, 3, ... until the supply runs out. The number of iterations is bounded by the point where the arithmetic series sum exceeds candies, which is roughly √(2 × candies). This makes the loop efficient even when the candy count is large. Use this approach when you want the most readable solution and minimal mathematical reasoning.
Approach 2: Mathematical Distribution (Time: O(n), Space: O(n))
The candy sequence forms a clear arithmetic progression: 1 + 2 + 3 + ... + k. Instead of simulating each step, compute how many full distributions occur before candies run out. The sum of the first k numbers is k(k+1)/2, which allows you to determine the maximum k such that the total distributed candies do not exceed the available amount.
Once k is known, compute how many complete rounds each person receives and how many extra distributions remain. Each person's candies can be derived using arithmetic series formulas rather than step-by-step updates. The final remainder after k(k+1)/2 candies is added to the next person in order.
This solution relies heavily on mathematical reasoning and properties of arithmetic series. It avoids explicit simulation and instead derives each person's share analytically. The complexity becomes linear in num_people because the algorithm only calculates results for each person once.
Recommended for interviews: Start with the simulation approach to show you understand the distribution mechanics. It is simple, reliable, and easy to code under pressure. After that, discuss the mathematical optimization that leverages arithmetic progression sums. Interviewers often appreciate seeing both the straightforward simulation and the optimized math-based reasoning.
This approach iteratively distributes candies to people in a sequence, considering one cycle at a time until all candies are allocated.
The C solution utilizes a simple while loop for the distribution of candies. It tracks how many candies to give based on a running total. The modulo operation (%num_people) ensures allocation is cycled through the people repeatedly until candies run out.
Time Complexity: O(sqrt(2 * candies)). This is because the linear sum of the sequence continues until all candies are exhausted, which resembles the behavior of an arithmetic series.
Space Complexity: O(num_people), since we maintain an array to store the number of candies for each person.
Using a mathematical approach, calculate full rounds of distribution first to optimize the solution as opposed to simulating step-by-step distribution.
Although this solution follows a similar process to the iterative one, it stops calculating after wrapping through all the necessary candies in full cycles using arithmetic logic for each complete set of distributions.
Time Complexity: O(sqrt(2 * candies)) due to converging arithmetic series.
Space Complexity: O(num_people).
We can directly simulate the process of each person receiving candies, following the rules described in the problem.
The time complexity is O(max(\sqrt{candies}, num_people)), and the space complexity is O(num_people). Here, candies is the number of candies.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Iterative Distribution Approach | Time Complexity: O(sqrt(2 * candies)). This is because the linear sum of the sequence continues until all candies are exhausted, which resembles the behavior of an arithmetic series. Space Complexity: O(num_people), since we maintain an array to store the number of candies for each person. |
| Mathematical Distribution Approach | Time Complexity: O(sqrt(2 * candies)) due to converging arithmetic series. Space Complexity: O(num_people). |
| Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Distribution (Simulation) | O(√candies) | O(n) | Best for clarity and quick implementation during interviews |
| Mathematical Distribution | O(n) | O(n) | When you want a formula-based optimized solution without step simulation |
LeetCode 1103. Distribute Candies to People (Algorithm Explained) • Nick White • 13,111 views views
Watch 9 more video solutions →Practice Distribute Candies to People with our built-in code editor and test cases.
Practice on FleetCode