Leetcode 1103. Distribute Candies to People

Problem Explanation

In this problem, we are given the task to distribute a given number of candies among the specified number of people. The distribution must follow specific rules. For the first iteration, the 1st person receives 1 candy, the second person receives 2 candies, the 3rd person receives 3 candies and so on until we have distributed to all the people.

For the next round, the number of candies given per person is increased by the total number of people. So, the 1st person will receive num_people + 1 candies, the second person will receive num_people + 2 candies, and so on. This rule continues until we run out of candies.

Finally, we are to return an array that represents the distribution of candies.

Solution Explanation

To solve this problem, we first initialize an empty array with size equal to num_people. Then, we calculate the number of complete turns we can do with the given candies (which we denote by rows).

Next, we distribute the candies in these complete turns. In each row, the person at index i will receive (accumN + rows * (i + 1)) candies.

After that, we calculate the number of candies left after all complete turns have been distributed. Then we distribute these remaining candies one by one to each person, starting from the first person, until all the candies are distributed.

Python Solution:

3class Solution:
4    def distributeCandies(self, candies: int, num_people: int) -> List[int]:
5        candies_distribute = [0]*num_people
6        round= 0
7        while candies:
8            for i in range(len(candies_distribute)):
9                if candies <= round*num_people + i+1:
10                    candies_distribute[i] += candies
11                    candies = 0
12                    break
13                else:
14                    candies_distribute[i] += round*num_people + i + 1
15                    candies -= round*num_people + i + 1
16            round += 1
17        return candies_distribute

Java Solution:

3class Solution {
4    public int[] distributeCandies(int candies, int num_people) {
5        int[] result = new int[num_people];
6        int i = 0;
7        while (candies > 0) {
8            result[i % num_people] += Math.min(candies, i + 1);
9            candies -= i + 1;
10            i++;
11        }
12        return result;
13    }

JavaScript Solution:

3var distributeCandies = function(candies, num_people) {
4    let result = new Array(num_people).fill(0), i = 0;
5    while(candies > i){
6        result[i % num_people] += ++i;
7        candies -= i;
8    }
9    result[(i - 1) % num_people] += candies;
10    return result;

C++ Solution:

3class Solution {
5    vector<int> distributeCandies(int candies, int num_people) {
6        vector<int> result(num_people, 0);
7        for(int i = 0; candies > 0; candies -= i)
8            result[i % num_people] += min(candies, ++i);
9        return result;
10    }

C# Solution:

3public class Solution {
4    public int[] DistributeCandies(int candies, int num_people) {
5        int[] result = new int[num_people];
6        int i = 0;
7        while (candies > 0) {
8            result[i % num_people] += Math.Min(candies, i + 1);
9            candies -= i + 1;
10            i++;
11        }
12        return result;
13    }

Each of the solutions above follows the algorithm explained in the solution explanation. Depending on the programming language being used, the syntax and constructs may be slightly different, but the concept remains the same.

Although all the four solutions have almost the same performance speed, the python version is the easiest to understand, but it still follows the same logic as the other versions.

All the solutions first initialize an array with size equal to num_people and then keep distributing candies by decreasing the total number of candies.

The final computed array 'candies_distribute' holds the solution for this problem, that is the no. of candies each child gets.

Overall, it's a straightforward problem that requires an understanding of loops, array manipulation and some smart mathematics to quickly calculate how candies should be distributed in each turn.

Key things to remember while solving the problem:

  1. Initialize an empty array with size equal to num_people to store the distribution of candies for each person.
  2. Calculate the no. of complete turns that can be done initially.
  3. After that, distribute the remaining candies one-by-one until all candies are distributed.
  4. Task has to be done using loops, array manipulation, conditional statements and basic operators. Direct library or function support is not available for this problem, therefore these basic programming skills are essential to solve it.

By practicing such problems, one can get a better grip on basic programming constructs like loops, arrays and conditional statements. Furthermore, such problems also enhance the problem solving and mathematical skills of the learner as it involves the strategic distribution of candies among several people following specific rules.

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

TA 👨‍🏫