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.

Examples

Example 1

1
2
3
4
5
6
7

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

1
2
3
4
5
6
7

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

Solution

Method 1 – Simulation

Intuition

We distribute candies in increasing order, looping through people, and giving each the minimum of the next expected amount or the remaining candies. This process is repeated until all candies are distributed.

Approach

  1. Initialize an array ans of size num_people with zeros.
  2. Use a variable give to track the next number of candies to give (starting from 1).
  3. Loop through the people in a round-robin fashion:
    • Give min(give, candies) candies to the current person.
    • Subtract the given candies from candies.
    • Increment give by 1.
    • Move to the next person (wrap around if needed).
  4. Stop when all candies are distributed.
  5. Return the ans array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    vector<int> distributeCandies(int candies, int num_people) {
        vector<int> ans(num_people, 0);
        int give = 1, i = 0;
        while (candies > 0) {
            int to_give = min(give, candies);
            ans[i % num_people] += to_give;
            candies -= to_give;
            give++;
            i++;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func distributeCandies(candies int, numPeople int) []int {
    ans := make([]int, numPeople)
    give, i := 1, 0
    for candies > 0 {
        toGive := give
        if toGive > candies {
            toGive = candies
        }
        ans[i%numPeople] += toGive
        candies -= toGive
        give++
        i++
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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

class Solution {
    fun distributeCandies(candies: Int, numPeople: Int): IntArray {
        val ans = IntArray(numPeople)
        var give = 1
        var i = 0
        var c = candies
        while (c > 0) {
            val toGive = minOf(give, c)
            ans[i % numPeople] += toGive
            c -= toGive
            give++
            i++
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def distributeCandies(self, candies: int, num_people: int) -> list[int]:
        ans = [0] * num_people
        give = 1
        i = 0
        while candies > 0:
            to_give = min(give, candies)
            ans[i % num_people] += to_give
            candies -= to_give
            give += 1
            i += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
    pub fn distribute_candies(candies: i32, num_people: i32) -> Vec<i32> {
        let mut ans = vec![0; num_people as usize];
        let mut give = 1;
        let mut c = candies;
        let mut i = 0;
        while c > 0 {
            let to_give = give.min(c);
            ans[i % num_people as usize] += to_give;
            c -= to_give;
            give += 1;
            i += 1;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    distributeCandies(candies: number, num_people: number): number[] {
        const ans = Array(num_people).fill(0);
        let give = 1, i = 0;
        while (candies > 0) {
            const toGive = Math.min(give, candies);
            ans[i % num_people] += toGive;
            candies -= toGive;
            give++;
            i++;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(sqrt(candies)), since the number of rounds is about the square root of candies (sum of 1+2+…+k <= candies).
  • 🧺 Space complexity: O(num_people), for the answer array.