Distribute Candies to People solution and explanation
9 more videos on this problem
LeetCode 1103. Distribute Candies to People (Algorithm Explained)Nick White · 7:35 · 13K views
Distribute Candies to People | LeetCode 1103 | C++, Java, PythonKnowledge Center · 9:39 · 7K views
Distribute Candies to People | Leet code 1103 | Theory explained + Python codeSai Anish Malla · 12:46 · 1K views
distribute candies to people leetcode | leetcode 1103 | Osqrt(candies)Naresh Gupta · 8:42 · 1K views
Distribute Candies to People | Day 17 | [ August LeetCoding Challenge ] [ Leetcode #1103 ] [ 2020 ]Algorithms Made Easy · 3:43 · 581 views
Leetcode - Distribute Candies to People (Python)Timothy H Chang · 5:10 · 423 views
LC1103 Distribute Candies to PeopleCSE Society · 11:09 · 323 views
Distribute Candies to People | Leetcode August Challenge (Day17) | Problem 1103Coding Decoded · 6:02 · 201 views
1103. Distribute Candies To People (Updated Video in Description) (Leetcode Easy)Programming Live with Larry · 37:04 · 186 views
Daily Leetcode #139: Aug 17, 2020 - 1103. Distribute Candies to PeopleProgramming Live with Larry · 21:59 · 155 views
The problem
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
Approach overview
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.
Approach 1: Iterative Distribution Approach
This approach iteratively distributes candies to people in a sequence, considering one cycle at a time until all candies are allocated.
def distribute_candies(candies, num_people):
result = [0] * num_people
i = 0
amount = 1
while candies > 0:
result[i % num_people] += min(candies, amount)
candies -= amount
amount += 1
i += 1
return result
# Example usage:
candies = 7
num_people = 4
print(distribute_candies(candies, num_people))import java.util.Arrays;
public class CandiesDistribution {
public static int[] distributeCandies(int candies, int num_people) {
int[] result = new int[num_people];
int i = 0;
int amount = 1;
while (candies > 0) {
result[i % num_people] += Math.min(candies, amount);
candies -= amount;
amount++;
i++;
}
return result;
}
public static void main(String[] args) {
int candies = 7, num_people = 4;
int[] result = distributeCandies(candies, num_people);
System.out.println(Arrays.toString(result));
}
}#include <iostream>
#include <vector>
using namespace std;
vector<int> distributeCandies(int candies, int num_people) {
vector<int> result(num_people, 0);
int i = 0;
int amount = 1;
while (candies > 0) {
result[i % num_people] += min(candies, amount);
candies -= amount;
amount++;
i++;
}
return result;
}
int main() {
int candies = 10;
int num_people = 3;
vector<int> result = distributeCandies(candies, num_people);
for (int num : result) {
cout << num << " ";
}
return 0;
}function distributeCandies(candies, num_people) {
const result = new Array(num_people).fill(0);
let i = 0;
let amount = 1;
while (candies > 0) {
result[i % num_people] += Math.min(candies, amount);
candies -= amount;
amount++;
i++;
}
return result;
}
// Example usage:
let candies = 7;
let num_people = 4;
console.log(distributeCandies(candies, num_people));#include <stdio.h>
void distributeCandies(int candies, int num_people, int result[]) {
int i = 0, amount = 1;
while (candies > 0) {
result[i % num_people] += (candies >= amount) ? amount : candies;
candies -= amount;
amount++;
i++;
}
}
int main() {
int candies = 7, num_people = 4;
int result[4] = {0};
distributeCandies(candies, num_people, result);
for (int i = 0; i < num_people; i++) {
printf("%d ", result[i]);
}
return 0;
}using System;
class Program {
public static int[] DistributeCandies(int candies, int numPeople) {
int[] result = new int[numPeople];
int i = 0;
int amount = 1;
while (candies > 0) {
result[i % numPeople] += Math.Min(candies, amount);
candies -= amount;
amount++;
i++;
}
return result;
}
static void Main() {
int candies = 10;
int numPeople = 3;
int[] result = DistributeCandies(candies, numPeople);
foreach (int num in result) {
Console.Write(num + " ");
}
}
}This Python code allocates candies using a list to hold each person's share. The use of % num_people guarantees round-robin allocation. The min function ensures the distributed quantity never exceeds the available candies.
Time Complexity: O(sqrt(2 * candies)).
Space Complexity: O(num_people), being simply the size of the list needed to store allocations.
Approach 2: Mathematical Distribution Approach
Using a mathematical approach, calculate full rounds of distribution first to optimize the solution as opposed to simulating step-by-step distribution.
def distribute_candies(candies, num_people):
result = [0] * num_people
i = 0
while candies > 0:
given = i + 1
result[i % num_people] += min(candies, given)
candies -= given
i += 1
return result
# Example usage:
candies = 7
num_people = 4
print(distribute_candies(candies, num_people))import java.util.Arrays;
public class CandiesDistribution {
public static int[] distributeCandies(int candies, int num_people) {
int[] result = new int[num_people];
int i;
for (i = 0; candies > 0; i++) {
int give = i + 1;
if (candies < give) {
give = candies;
}
result[i % num_people] += give;
candies -= give;
}
return result;
}
public static void main(String[] args) {
int candies = 7, num_people = 4;
int[] result = distributeCandies(candies, num_people);
System.out.println(Arrays.toString(result));
}
}#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
vector<int> distributeCandies(int candies, int num_people) {
vector<int> result(num_people, 0);
int i;
for (i = 0; candies > 0; i++) {
int give = i + 1;
if (candies < give) {
give = candies;
}
result[i % num_people] += give;
candies -= give;
}
return result;
}
int main() {
int candies = 10, num_people = 3;
vector<int> result = distributeCandies(candies, num_people);
for (int num : result) {
cout << num << " ";
}
return 0;
}function distributeCandies(candies, num_people) {
const result = new Array(num_people).fill(0);
let i = 0;
while (candies > 0) {
let give = i + 1;
if (candies < give) give = candies;
result[i % num_people] += give;
candies -= give;
i++;
}
return result;
}
// Example usage:
let candies = 7;
let num_people = 4;
console.log(distributeCandies(candies, num_people));#include <stdio.h>
#include <math.h>
void distributeCandies(int candies, int num_people, int result[]) {
int i;
for (i = 0; candies > 0; i++) {
int give = i + 1;
if (candies < give) {
give = candies;
}
result[i % num_people] += give;
candies -= give;
}
}
int main() {
int candies = 7, num_people = 4;
int result[4] = {0};
distributeCandies(candies, num_people, result);
for (int i = 0; i < num_people; i++) {
printf("%d ", result[i]);
}
return 0;
}using System;
class Program {
public static int[] DistributeCandies(int candies, int numPeople) {
int[] result = new int[numPeople];
int i = 0;
while (candies > 0) {
int give = i + 1;
if (candies < give) give = candies;
result[i % numPeople] += give;
candies -= give;
i++;
}
return result;
}
static void Main() {
int candies = 10;
int numPeople = 3;
int[] result = DistributeCandies(candies, numPeople);
foreach (int num in result) {
Console.Write(num + " ");
}
}
}This Python solution effectively reduces the operational complexity by calculating in larger blocks, then using an arithmetic method to fill any remaining candies. It allows for quicker transition between distribution cycles.
Time Complexity: O(sqrt(2 * candies)).
Space Complexity: O(num_people).
Approach 3: Simulation
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.
function distributeCandies(candies: number, num_people: number): number[] {
const ans: number[] = Array(num_people).fill(0);
for (let i = 0; candies > 0; ++i) {
ans[i % num_people] += Math.min(candies, i + 1);
candies -= Math.min(candies, i + 1);
}
return ans;
}func distributeCandies(candies int, num_people int) []int {
ans := make([]int, num_people)
for i := 0; candies > 0; i++ {
ans[i%num_people] += min(candies, i+1)
candies -= min(candies, i+1)
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Distribution Approach | Time Complexity: O(sqrt(2 * candies)). Space Complexity: O(num_people), being simply the size of the list needed to store allocations. |
| Mathematical Distribution Approach | Time Complexity: O(sqrt(2 * candies)). Space Complexity: O(num_people). |
| Simulation | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Distribute Candies to People easy or hard?
Distribute Candies to People is classified as an Easy problem on LeetCode with an acceptance rate around 67%. The core idea is simple simulation, while an optional optimization involves recognizing the arithmetic series pattern in the distribution sequence.
Distribute Candies to People Python/Java solution
Both Python and Java implementations typically follow the same simulation logic. Maintain an array for results, iterate with an increasing give counter, and assign candies using min(remaining, give). Continue until candies reach zero. The same logic translates directly to C++, JavaScript, and C#.
How to solve Distribute Candies to People in O(n)?
Use arithmetic progression formulas. First compute the maximum k such that k(k+1)/2 ≤ candies, representing how many distributions happen in total. Then determine how many full rounds each person receives and calculate their candies using series sums. Finally distribute the remaining candies to the next person.
What is the best approach for Distribute Candies to People?
The simulation approach is usually the best starting point. Iterate through people in a circular manner and give increasing candy amounts until the supply runs out. This solution runs in about O(√candies) time and uses O(n) space for the result array. A mathematical approach can further optimize reasoning using arithmetic series formulas.
Is Distribute Candies to People asked at Google/Amazon/Meta?
This problem is categorized as an easy math and simulation problem and commonly appears in coding practice sets similar to questions used in interviews at companies like Amazon and Google. While not one of the hardest interview questions, it tests understanding of loops, arithmetic sequences, and reasoning about distributions.
What data structure is used in Distribute Candies to People?
The main data structure is a simple array of size num_people that stores how many candies each person receives. The algorithm updates array indices in a circular manner using modulo arithmetic while distributing candies sequentially.
What is the time complexity of Distribute Candies to People?
The iterative simulation runs in approximately O(√candies) time because the number of distributions follows the sequence 1 + 2 + 3 + ... until it exceeds the candy count. The mathematical approach computes the result directly using arithmetic series and runs in O(n) time where n is the number of people.