# Distribute Candies to People
**Difficulty:** EASY
[External](https://leetcode.com/problems/distribute-candies-to-people)
Canonical: https://scaleengineer.com/dsa/problems/distribute-candies-to-people
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
---
## 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

# Approaches
## Simple Simulation
This approach directly simulates the process described in the problem. We maintain the current number of candies to give and the index of the person to receive them. In a loop, we distribute candies turn by turn until we run out.
**Time:** O(sqrt(candies)). Let K be the number of turns. The total candies distributed is the sum of the first K integers, which is `K*(K+1)/2`. This sum is approximately equal to the initial `candies`. Therefore, `K^2` is proportional to `candies`, and `K` (the number of loop iterations) is proportional to `sqrt(candies)`. · **Space:** O(num_people) to store the result array.
**Pros:** Simple to understand and implement.; Works correctly for all valid inputs.
**Cons:** Can be slow if `candies` is very large (e.g., close to 10^9), as the number of iterations would be around 31,622. This might lead to a 'Time Limit Exceeded' error on some platforms, although it's generally acceptable.
### Explanation
This method follows the problem description literally. We initialize an integer array `ans` of size `num_people` with all elements as 0. We also use a variable `give` to track the number of candies to be distributed in the current turn, starting from 1, and an index `i` to point to the current person in the row, starting from 0.

We loop as long as we have candies left. In each iteration, we check if the remaining `candies` are enough for the current turn. If `candies` is less than `give`, the current person receives all the remaining `candies`. Otherwise, they receive `give` candies. We update the person's total in the `ans` array and decrement the total `candies`. Then, we prepare for the next turn by incrementing `give` and moving to the next person by updating the index `i` (wrapping around to the start of the row if necessary).

```java
class Solution {
    public int[] distributeCandies(int candies, int num_people) {
        int[] ans = new int[num_people];
        int give = 1;
        int i = 0;
        while (candies > 0) {
            int candiesToGive = Math.min(candies, give);
            ans[i] += candiesToGive;
            candies -= candiesToGive;
            give++;
            i = (i + 1) % num_people;
        }
        return ans;
    }
}
```
### Algorithm
- Create a result array `ans` of size `num_people` and initialize all its elements to 0.
- Initialize `give = 1` to track the number of candies for the current turn.
- Initialize `i = 0` as the index for the current person.
- Start a loop that continues as long as `candies > 0`.
- Inside the loop, determine the number of candies to give in this turn: `candiesToGive = min(candies, give)`.
- Add `candiesToGive` to `ans[i]`.
- Decrease `candies` by `candiesToGive`.
- Increment `give` by 1 for the next turn.
- Update the person index: `i = (i + 1) % num_people`.
- After the loop terminates, return the `ans` array.

## O(n) Mathematical Approach
This approach is a significant optimization over simulation. By analyzing the mathematical patterns of the distribution, we can calculate the result in time proportional to the number of people, which is much faster than simulating each candy handout. The key is to determine the total number of gifts given, and then use arithmetic series formulas to find each person's share from the completed rounds.
**Time:** O(num_people). The calculation of `k` (total turns) is O(1). The main work is a single loop that iterates `num_people` times to calculate the final distribution for each person. All calculations inside the loop are O(1). Since `num_people` is much smaller than `sqrt(candies)` for large `candies`, this is the most efficient approach. · **Space:** O(num_people) to store the result array.
**Pros:** Extremely efficient, with a time complexity independent of the number of candies.; Avoids potential 'Time Limit Exceeded' errors for very large inputs.
**Cons:** The logic is more complex and relies on mathematical formulas for arithmetic series.; Requires careful handling of large numbers (using `long` in Java) to prevent integer overflow during intermediate calculations.
### Explanation
First, we determine the total number of successful turns, `k`, where in each turn `t` (from 1 to `k`), we give `t` candies. The total candies given after `k` turns is `1 + 2 + ... + k = k*(k+1)/2`. We need to find the largest `k` such that `k*(k+1)/2 <= candies`.

This inequality `k^2 + k - 2*candies <= 0` can be solved using the quadratic formula. The largest integer `k` is `floor(sqrt(2*candies + 0.25) - 0.5)`. This gives us the total number of gifts handed out.

With `k` total gifts, we can determine the number of full rounds of distribution. A full round gives candies to all `num_people`. The number of full rounds is `p = k / num_people`.

The number of people who receive gifts in the final, incomplete round is `extra = k % num_people`.

The candies remaining after `k` gifts are given out is `remaining = candies - k*(k+1)/2`.

Now, we can calculate the candies for each person `i` (0-indexed):
- **Candies from full rounds:** In `p` full rounds, person `i` receives `(i+1), (i+1)+n, ..., (i+1)+(p-1)n`. This is an arithmetic series with sum `p*(i+1) + n*p*(p-1)/2`.
- **Candies from the final partial round:** If person `i` is one of the `extra` people in the final round (`i < extra`), they receive an additional gift of `p*n + (i+1)` candies.
- **Leftover candies:** The `remaining` candies are all given to the person who would have received the `(k+1)`-th gift, which is person at index `extra`.

We sum these parts for each person. Note that `long` should be used for intermediate calculations to avoid integer overflow.

```java
class Solution {
    public int[] distributeCandies(int candies, int num_people) {
        // Find the largest k such that 1 + 2 + ... + k <= candies
        // k*(k+1)/2 <= candies  => k^2 + k - 2*candies <= 0
        // Solving for k gives k <= (sqrt(8*candies + 1) - 1) / 2
        // which is equivalent to floor(sqrt(2*candies + 0.25) - 0.5)
        long k = (long)(Math.sqrt(2.0 * candies + 0.25) - 0.5);

        long remaining_candies = (long)candies - (k * (k + 1) / 2);

        // Number of full rounds
        long p = k / num_people;
        // Number of people in the last partial round
        int extra_people = (int)(k % num_people);

        int[] ans = new int[num_people];

        for (int i = 0; i < num_people; i++) {
            // Candies from p full rounds for person i
            // They get (i+1), (i+1)+n, ..., (i+1)+(p-1)n
            // Sum = p*(i+1) + n*(0+1+...+(p-1)) = p*(i+1) + n*p*(p-1)/2
            long total = p * (i + 1) + (long)num_people * p * (p - 1) / 2;
            
            // Candies from the last partial round (if person i is in it)
            if (i < extra_people) {
                total += p * num_people + (i + 1);
            }
            ans[i] = (int)total;
        }

        // The very last person gets all remaining candies
        ans[extra_people] += (int)remaining_candies;

        return ans;
    }
}
```
### Algorithm
- Calculate `k`, the total number of gifts given, using the formula: `k = floor(sqrt(2*candies + 0.25) - 0.5)`.
- Calculate the number of full rounds `p = k / num_people`.
- Calculate the number of people in the final partial round `extra = k % num_people`.
- Calculate the candies left over after `k` gifts: `remaining = candies - k*(k+1)/2`.
- Initialize a result array `ans`.
- For each person `i` from `0` to `num_people - 1`:
  - Calculate candies from `p` full rounds: `full_round_candies = p*(i+1) + num_people*p*(p-1)/2`.
  - Calculate candies from the partial round: `partial_round_candies = (i < extra) ? (p*num_people + i + 1) : 0`.
  - Set `ans[i] = full_round_candies + partial_round_candies`.
- Add the remaining candies to the next person in line: `ans[extra] += remaining`.
- Return `ans`.

# Solutions
### Java

```java
class Solution {
public
  int[] distributeCandies(int candies, int num_people) {
    int[] ans = new int[num_people];
    for (int i = 0; candies > 0; ++i) {
      ans[i % num_people] += Math.min(candies, i + 1);
      candies -= Math.min(candies, i + 1);
    }
    return ans;
  }
}

```

### Python

```python
class Solution:
    def distributeCandies(self, candies: int, num_people: int) -> List[int]: ans = [0] * num_people i = 0 while candies: ans[i % num_people] += min(candies, i + 1) candies -= min(candies, i + 1) i += 1 return ans

```

### CPP

```cpp
class Solution {
public:
  vector<int> distributeCandies(int candies, int num_people) {
    vector<int> ans(num_people);
    for (int i = 0; candies > 0; ++i) {
      ans[i % num_people] += min(candies, i + 1);
      candies -= min(candies, i + 1);
    }
    return ans;
  }
};

```