1103. Distribute Candies to People
Problem Description
In this problem, we have a certain number of candies
that need to be distributed to num_people
people arranged in a row. The distribution starts with the first person receiving one candy, the second person receiving two candies, and so on, increasing the count of candies by one for each subsequent person until the n
th person receives n
candies. After reaching the last person, the distribution continues from the first person again, but this time each person gets one more candy than the previous cycle (so the first person now gets n+1
candies, the second gets n+2
, and so on). This process repeats until we run out of candies. If there are not enough candies to give the next person in the sequence their "full" amount, they receive the remaining candies, and the distribution ends.
The goal is to return an array of length num_people
, with each element representing the total number of candies that each person receives at the end of the distribution process.
Intuition
To solve this problem, we want to simulate the described candy distribution process. We keep handing out candies until we have none left. Each person gets a certain number of candies based on the round of distribution we are in. In the first round, person 1 gets 1 candy, person 2 gets 2 candies, and so on. Once we reach num_people
, we wrap around and start from person 1 again, increasing the amount of candy given out by num_people
each round.
The solution involves iterating over the people in a loop and incrementing the number of candies each person gets by the distribution rule given. We maintain a counter i
to keep track of how many candies have been given out so far, and a list ans
to store the total candies for each person.
With each person's turn, we give out the number of candies equal to the counter i + 1
, but if we have fewer candies left than i + 1
, we give out all the remaining candies. After that, we update the total number of candies left by subtracting the number given out. If the candies finish during someone's turn, we stop the distribution and return our ans
list to show the final distribution of candies.
The intuition is to replicate the physical process of handing out the candies in a loop, ensuring that conditions such as running out of candies are properly handled.
Learn more about Math patterns.
Solution Approach
The solution to this problem uses a simple iterative approach as our algorithm. Here are the steps and the reasoning in detail:
-
Initialize the Answer List: We start by initializing an array
ans
of lengthnum_people
with all elements set to 0. This array will be used to keep track of the number of candies each person receives. -
Starting the Distribution: We need to keep track of two things - the index of the person to whom we're currently giving candies, and the number of candies we're currently handing out. We start the distribution by setting a counter
i
to 0, which will increase with each iteration to represent the amount of candy to give. -
Iterative Distribution: We use a
while
loop to continue distributing candies until we run out (candies > 0
). During each iteration of the loop:- Compute
i % num_people
to find the index of the current person. This ensures that after the last person, we start again from the first person. - Determine the number of candies to give to the current person. We use
min(candies, i + 1)
to decide this amount because we either givei + 1
candies or the remaining candies if we have less thani + 1
. - Subtract the number of distributed candies from
candies
. - Increment
i
by 1 to update the count for the next iteration.
- Compute
-
Updating Answer List: In each iteration, update
ans[i % num_people]
with the number of candies distributed in that iteration. -
Handling Remaining Candies: If we deplete our supply of
candies
, we give out the remaining candies to the last person. This is built into the allocation step withmin(candies, i + 1)
. -
Returning the Final Distribution: Once the loop ends (no more candies are left), we exit the loop. The array
ans
now contains the total number of candies received by each person, which we return as the final answer.
This problem does not require any complex data structures or patterns. The concept is straightforward and only uses basic array manipulation to achieve the goal. It focuses on handling the loop correctly and ensuring that the distribution of candies is done according to the specified rules.
1class Solution:
2 def distributeCandies(self, candies: int, num_people: int) -> List[int]:
3 ans = [0] * num_people # Initialize the answer list
4 i = 0 # Counter for the distribution process
5 # Distribute candies until we run out
6 while candies:
7 # Give out min(candies, i + 1) candies to the (i % num_people)th person
8 ans[i % num_people] += min(candies, i + 1)
9 candies -= min(candies, i + 1) # Subtract the candies given from the total
10 i += 1 # Move to the next person
11
12 return ans # Return the final distribution
The solution makes effective use of modulo operation to cycle through the indices repeatedly while the while
loop condition ensures that the distribution halts at the right time.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use a small example to illustrate the solution approach.
Suppose we have candies = 7
and num_people = 4
.
We want to distribute these candies across 4 people as described. Let's walk through the process using the provided algorithm.
- Initialize the Answer List:
ans = [0, 0, 0, 0]
- Starting the Distribution:
candies = 7
- Distribution counter
i = 0
- Iterative Distribution:
- During the first iteration (
i = 0
):- Current person index:
0 % 4 = 0
(first person) - Candies to give out:
min(7, 0 + 1) = 1
- Remaining candies:
7 - 1 = 6
- Updated
ans
list:[1, 0, 0, 0]
- Increment
i
to1
- Current person index:
- In the second iteration (
i = 1
):- Current person index:
1 % 4 = 1
(second person) - Candies to give out:
min(6, 1 + 1) = 2
- Remaining candies:
6 - 2 = 4
- Updated
ans
list:[1, 2, 0, 0]
- Increment
i
to2
- Current person index:
- In the third iteration (
i = 2
):- Current person index:
2 % 4 = 2
(third person) - Candies to give out:
min(4, 2 + 1) = 3
- Remaining candies:
4 - 3 = 1
- Updated
ans
list:[1, 2, 3, 0]
- Increment
i
to3
- Current person index:
- In the fourth iteration (
i = 3
):- Current person index:
3 % 4 = 3
(fourth person) - Candies to give out:
min(1, 3 + 1) = 1
- Remaining candies:
1 - 1 = 0
(no more candies) - Updated
ans
list:[1, 2, 3, 1]
- Candies are now depleted, we stop the distribution.
- Current person index:
- During the first iteration (
- Return the Final Distribution:
- The final
ans
list is[1, 2, 3, 1]
.
- The final
Each element in the ans
list represents the total number of candies each person receives after the distribution is done. The algorithm successfully mimics the handing out of candies until there are no more left, while following the rules set out in the problem description.
Solution Implementation
1from typing import List
2
3class Solution:
4 def distributeCandies(self, candies: int, num_people: int) -> List[int]:
5 # Initialize a list to hold the number of candies each person will receive
6 distribution = [0] * num_people
7 # Initialize an index variable to distribute candies to the people in order
8 index = 0
9
10 # Continue distribution until there are no more candies left
11 while candies > 0:
12 # Calculate the number of candies to give: either 1 more than the current index
13 # or the remaining candies if fewer than that number remain
14 give = min(candies, index + 1)
15 # Distribute the candies to the current person
16 distribution[index % num_people] += give
17 # Subtract the number of candies given from the remaining total
18 candies -= give
19 # Move to the next person for the next round of distribution
20 index += 1
21
22 # Return the final distribution
23 return distribution
24
1class Solution {
2 public int[] distributeCandies(int candies, int numPeople) {
3 // Initialize the answer array with the size equal to numPeople.
4 // All elements are initialized to 0.
5 int[] distribution = new int[numPeople];
6
7 // Initialize the index for the current person
8 // and the amount to give out to the current person
9 int index = 0;
10 int currentCandyAmount = 1;
11
12 // Use a loop to distribute the candies until all candies are distributed
13 while (candies > 0) {
14 // Calculate the index for the current distribution round
15 // It cycles back to 0 when it reaches numPeople
16 int personIndex = index % numPeople;
17
18 // Determine the number of candies to give out
19 // It is the minimum of either the remaining candies or the current amount
20 int candiesToGive = Math.min(candies, currentCandyAmount);
21
22 // Update the candies count for the current person
23 distribution[personIndex] += candiesToGive;
24
25 // Subtract the candies given out from the total count of remaining candies
26 candies -= candiesToGive;
27
28 // Move to the next person and increment the candy amount
29 index++;
30 currentCandyAmount++;
31 }
32
33 // Return the distribution result
34 return distribution;
35 }
36}
37
1#include <vector>
2#include <algorithm> // for std::min function
3
4class Solution {
5public:
6 /**
7 * Distributes candies among people in a loop.
8 *
9 * @param candies Number of candies to distribute.
10 * @param num_people Number of people to distribute the candies to.
11 * @return A vector<int> containing the distribution of candies.
12 */
13 vector<int> distributeCandies(int candies, int num_people) {
14 vector<int> distribution(num_people, 0); // Create a vector with num_people elements, all initialized to 0
15 int i = 0; // Initialize a counter to track the number of candies given
16
17 // Continue distributing candies until none are left
18 while (candies > 0) {
19 // Calculate the index of the current person and the amount of candies to give
20 int index = i % num_people;
21 int give = std::min(candies, i + 1); // The number of candies to give is the lesser of the remaining candies and the current count
22
23 distribution[index] += give; // Distribute the candies to the current person
24 candies -= give; // Decrease the total candy count
25
26 ++i; // Move to the next candy count
27 }
28
29 return distribution; // Return the final distribution
30 }
31};
32
1// Function to distribute candies among people in a way that the ith allocation
2// increases by 1 candy
3function distributeCandies(candies: number, numPeople: number): number[] {
4 // Initialize an answer array to hold the number of candies for each person,
5 // starting with zero candies for each person
6 const distribution: number[] = new Array(numPeople).fill(0);
7
8 // Variable to track the current distribution round
9 let currentDistribution = 0;
10
11 // Continue distributing candies until none are left
12 while (candies > 0) {
13 // Calculate the current person's index by using modulo with numPeople.
14 // This ensures we loop over the array repeatedly
15 const currentIndex = currentDistribution % numPeople;
16
17 // Determine the number of candies to give in this round. It is the minimum
18 // of the remaining candies and the current distribution amount (1-indexed)
19 const candiesToGive = Math.min(candies, currentDistribution + 1);
20
21 // Update the distribution array for the current person
22 distribution[currentIndex] += candiesToGive;
23
24 // Subtract the given candies from the total remaining candies
25 candies -= candiesToGive;
26
27 // Move on to the next round of distribution
28 currentDistribution++;
29 }
30
31 // Return the final distribution of candies
32 return distribution;
33}
34
Time and Space Complexity
The time complexity of the given code can be determined by the while loop, which continues until all candies
are distributed. In each iteration of the loop, i
is incremented by 1
, and the amount of candies distributed is also incremented by 1
until all candies are exhausted. This forms an arithmetic sequence from 1
to n
where n
is the turn where the candies run out. The total number of candies distributed by this sequence can be represented by the sum of the first n
natural numbers formula n*(n+1)/2
. So the time complexity is governed by the smallest n
such that n*(n+1)/2 >= candies
. Therefore, the time complexity is O(sqrt(candies)) because we need to find an n
such that n^2
is asymptotically equal to the total number of candies
.
The space complexity of the code is determined by the list ans
that has a size equal to num_people
. Since the size of this list does not change and does not depend on the number of candies, the space complexity is O(num_people), which is the space required to store the final distribution of the candies among the people.
Learn more about how to find time and space complexity quickly using problem constraints.
Depth first search is equivalent to which of the tree traversal order?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first