Distribute Candies to People

Difficulty: Easy | Acceptance: 67.60% | Paid: No Topics: Math, Simulation

We distribute candies to people sitting in a circle. We start by giving 1 candy to the first person, 2 candies to the second person, and so on until we give n candies to the nth person. Then, we go back to the start of the circle and give n + 1 candies to the first person, n + 2 candies to the second person, and so on.

This process continues until we run out of candies. The last person may receive fewer candies than required (i.e., if there are fewer candies left than the current turn’s amount, they receive all remaining candies).

Given two integers candies and num_people, return an array of length num_people where result[i] is the number of candies the ith person received.

• Examples
• Constraints
• Approach 1: Simulation
• Approach 2: Mathematical Formula

Examples

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] += min(4,1) = 1, and the array is [1,2,3,1].

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 array is [5,2,3].

Constraints

0 <= candies <= 10^9
1 <= num_people <= 1000

Simulation

Intuition We can directly simulate the process of distributing candies. We iterate through the people in a circular fashion, giving the current number of candies to the current person, then decrementing the total candies and incrementing the amount to give in the next turn.

Steps

• Initialize a result array of size num_people with zeros.
• Initialize a variable current_candy to 1 and an index i to 0.
• Loop while candies is greater than 0.
• Calculate the amount to give: give = min(current_candy, candies).
• Add give to result[i % num_people].
• Subtract give from candies.
• Increment current_candy and i.

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

Complexity

• Time: O(√candies) — The number of turns is proportional to the square root of candies because 1 + 2 + … + k ≈ k²/2.
• Space: O(num_people) — To store the result.
• Notes: Simple to implement and sufficiently fast given the constraints.

Mathematical Formula

Intuition The distribution follows an arithmetic progression. We can calculate how many complete rounds of distribution happen and how many candies are distributed in those rounds using arithmetic series formulas. Then, we handle the remaining partial round.

Steps

• Find the number of complete rounds p. The sum of the first m integers is m(m+1)/2. We find the largest m such that this sum is ≤ candies. Then p = m // num_people.
• Calculate the base candies for each person i (0-indexed) after p full rounds. This is an arithmetic series: (i+1) + (i+1+num_people) + ... for p terms.
• Calculate the remaining candies after p full rounds.
• Distribute the remaining candies starting from the next term (p * num_people + 1) to the people until candies run out.

import math

class Solution:
    def distributeCandies(self, candies: int, num_people: int) -> list[int]:
        res = [0] * num_people
        # Find number of complete rounds p
        # m is the total number of turns if we gave 1, 2, 3... until candies ran out
        # m(m+1)/2 <= candies
        m = int((math.sqrt(2 * candies + 0.25) - 0.5))
        p = m // num_people
        
        # Base sum for each person
        for i in range(num_people):
            # AP: (i+1), (i+1)+n, ..., (i+1)+(p-1)n
            # Sum = p * (i+1) + n * p * (p-1) / 2
            res[i] = p * (i + 1) + num_people * p * (p - 1) // 2
        
        # Remaining candies
        used = p * num_people * (p * num_people + 1) // 2
        remaining = candies - used
        
        # Distribute remaining
        next_term = p * num_people + 1
        for i in range(num_people):
            if remaining <= 0: break
            give = min(remaining, next_term + i)
            res[i] += give
            remaining -= give
            
        return res

Complexity

• Time: O(num_people) — We iterate through the people array a constant number of times.
• Space: O(num_people) — To store the result.
• Notes: More efficient for very large candy counts, but requires careful handling of integer overflow (using 64-bit integers or BigInt).