Distribute Candies to People — Problem & Solution
Distribute Candies to People solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Distribute Candies to People is an easy coding problem on arrays, math and simulation, asked in Amazon interviews.
- Difficulty: Easy
- Topics: Arrays, Math, Simulation
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You have candies sweets to hand out to numPeople people standing in a row.
Go down the row giving 1 sweet to the first person, 2 to the second, and so on up to numPeople sweets to the last. Then start again from the first person, giving numPeople + 1, numPeople + 2, … and keep looping.
When fewer sweets remain than the next person is owed, that person gets all the remainder and the process stops. Return the final count each person holds.
Example 1
Input: candies = 7, numPeople = 4
Output: [1,2,3,1]
Explanation: 1, 2, 3 are given in full; only 1 sweet is left for the fourth person.
Example 2
Input: candies = 10, numPeople = 3
Output: [5,2,3]
Explanation: Round one gives 1,2,3; then the first person takes the remaining 4.
Example 3
Input: candies = 1, numPeople = 1
Output: [1]
Constraints
1 <= candies <= 10000000001 <= numPeople <= 1000
Hints for Distribute Candies to People
Hint 1
The loop runs until the sweets are gone — how many rounds is that at most?
Hint 2
The
k-th handout isk + 1sweets, so aftermhandouts you have spentm(m+1)/2. That caps the loop at aboutsqrt(2 · candies)steps.Hint 3
Use
min(owed, remaining)for each handout so the final partial gift is handled by the same line of code.
How to solve Distribute Candies to People
Straight simulation is fast enough: the handouts grow linearly, so the total number of them is on the order of sqrt(2 · candies) — about 45,000 even at the maximum.
Approach
- Allocate an array of
numPeoplezeros. - Track
give(the amount owed on this handout, starting at 1) andi(the handout index). - Each step, hand out
min(give, remaining)to personi % numPeople, subtract it from the remainder, then increment both counters. - Stop when nothing remains and return the array.
Why it works
Handing out min(give, remaining) collapses the "give everything that is left" rule into the ordinary case, so the loop needs no special final branch. The loop terminates because every iteration removes at least one sweet.
Complexity
- Time —
O(sqrt(candies) + numPeople) - Space —
O(numPeople)
Pitfalls
- Giving
giveunconditionally overshoots and leaves a negative remainder. - Resetting
giveto 1 at the start of each round is wrong — it keeps growing across rounds. - Indexing must wrap with
% numPeople, not stop at the end of the row.
Reference solution
Python
from typing import List
def distributeCandies(candies: int, numPeople: int) -> List[int]:
out = [0] * numPeople
give = 1
i = 0
while candies > 0:
g = give if give < candies else candies
out[i % numPeople] += g
candies -= g
give += 1
i += 1
return outJava
public static int[] distributeCandies(int candies, int numPeople) {
int[] out = new int[numPeople];
long give = 1;
int i = 0;
while (candies > 0) {
long g = Math.min(give, (long) candies);
out[i % numPeople] += (int) g;
candies -= (int) g;
give++;
i++;
}
return out;
}C++
vector<int> distributeCandies(int candies, int numPeople) {
vector<int> out(numPeople, 0);
long long give = 1;
int i = 0;
while (candies > 0) {
long long g = min(give, (long long) candies);
out[i % numPeople] += (int) g;
candies -= (int) g;
give++;
i++;
}
return out;
}JavaScript
var distributeCandies = function(candies, numPeople) {
const out = new Array(numPeople).fill(0);
let give = 1, i = 0;
while (candies > 0) {
const g = Math.min(give, candies);
out[i % numPeople] += g;
candies -= g;
give++;
i++;
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays