Code Implementation

class Solution:
    def distributeCandies(self, candies: int, num_people: int) -> list:
        res = [0] * num_people
        give = 1
        idx = 0
        while candies > 0:
            to_give = min(give, candies)
            res[idx % num_people] += to_give
            candies -= to_give
            give += 1
            idx += 1
        return res
      

class Solution {
public:
    vector<int> distributeCandies(int candies, int num_people) {
        vector<int> res(num_people, 0);
        int give = 1, idx = 0;
        while (candies > 0) {
            int to_give = min(give, candies);
            res[idx % num_people] += to_give;
            candies -= to_give;
            give++;
            idx++;
        }
        return res;
    }
};
      

class Solution {
    public int[] distributeCandies(int candies, int num_people) {
        int[] res = new int[num_people];
        int give = 1, idx = 0;
        while (candies > 0) {
            int toGive = Math.min(give, candies);
            res[idx % num_people] += toGive;
            candies -= toGive;
            give++;
            idx++;
        }
        return res;
    }
}
      

var distributeCandies = function(candies, num_people) {
    let res = new Array(num_people).fill(0);
    let give = 1, idx = 0;
    while (candies > 0) {
        let toGive = Math.min(give, candies);
        res[idx % num_people] += toGive;
        candies -= toGive;
        give++;
        idx++;
    }
    return res;
};
      

Problem Description

You are given an integer candies representing the total number of candies to distribute, and an integer num_people representing the number of people standing in a line. The candies are distributed in rounds: in each round, you give 1 candy to the first person, 2 to the second, and so on, until you run out of candies. If you reach the end of the line, you continue from the beginning, increasing the amount given each time. The process continues until all candies are distributed. The task is to return an array representing how many candies each person gets at the end.
Constraints:

• There is only one valid way to distribute candies: always give as much as possible to the next person in line.
• You must not reuse or skip any candies or people.

Thought Process

At first glance, this problem seems to require a simulation: just go through each person in order, handing out candies, and wrapping around when you reach the end of the line. Each time, the number of candies given increases by one.

However, it’s important to realize that the number of candies given to each person will be the sum of the candies they get in each round, and the process continues until we run out of candies. The main challenge is to keep track of how many candies to give next, not to exceed the total available.

Instead of focusing on a complicated formula, we can use a simple loop that hands out the minimum of the current "should give" and the remaining candies. This way, we avoid unnecessary complexity and ensure correctness.

Solution Approach

The approach is straightforward and simulates the distribution process:

• Initialize an array res of size num_people with all elements as 0. This array will store the candies each person receives.
• Set a variable give to 1, representing the number of candies to give in the current turn.
• Use an index idx to keep track of the current person (cycling back to 0 after the last person).
• While there are still candies left, repeat the following:
  • Give min(give, candies) candies to res[idx % num_people].
  • Subtract the given candies from candies.
  • Increment give by 1 for the next turn.
  • Increment idx to move to the next person.
• When all candies are distributed, return res.

This method ensures each person receives candies in increasing order, and the process wraps around the group as needed.

Example Walkthrough

Example:
candies = 10, num_people = 3

Step-by-step:

• Start: res = [0, 0, 0], give = 1, candies = 10
• Round 1: Give 1 to person 0 → res = [1, 0, 0], candies left: 9
• Round 2: Give 2 to person 1 → res = [1, 2, 0], candies left: 7
• Round 3: Give 3 to person 2 → res = [1, 2, 3], candies left: 4
• Round 4: Give 4 to person 0 → res = [5, 2, 3], candies left: 0

The process stops since there are no candies left. The result is [5, 2, 3].

Time and Space Complexity

Brute-force Approach:

• Each distribution step is O(1), but the number of steps depends on how quickly we run out of candies. In the worst case, it's roughly O(√candies) since the sum of the first k natural numbers is k(k+1)/2 ≈ candies.
• Space complexity is O(num_people) for the result array.

• The above approach is already efficient, as it only loops as many times as necessary to distribute all candies, which is optimal for this problem.
• There is no significant extra space used beyond the result array.

Summary

This problem is elegantly solved by simulating the distribution process, always giving the minimum of the next expected amount and the remaining candies. The solution is simple, intuitive, and avoids unnecessary calculations or data structures. The key insight is to increment the amount to give each time and wrap around the array, ensuring each person gets their fair share until the candies run out.