LeetCode 1103 - Distribute Candies to People

The problem describes a sequential candy distribution process across a row of people. We are given two integers, candies and numpeople. The goal is to simulate distributing candies in increasing order until all candies are exhausted.

leetcodeeasymathsimulation

LeetCode Problem 1103

Difficulty: 🟢 Easy
Topics: Math, Simulation

Solution

Problem Understanding

The problem describes a sequential candy distribution process across a row of people. We are given two integers, candies and num_people. The goal is to simulate distributing candies in increasing order until all candies are exhausted.

The distribution pattern follows a strict sequence. The first person receives 1 candy, the second person receives 2 candies, the third receives 3 candies, and so on. After reaching the last person in the row, the process wraps back to the beginning, but the candy count continues increasing rather than resetting.

For example, if there are 4 people, the first cycle distributes:

  • Person 0 gets 1
  • Person 1 gets 2
  • Person 2 gets 3
  • Person 3 gets 4

The second cycle continues with:

  • Person 0 gets 5
  • Person 1 gets 6
  • Person 2 gets 7
  • Person 3 gets 8

This continues until there are not enough candies left to fulfill the next intended gift. In that case, the current person simply receives all remaining candies.

The output must be an array of length num_people, where each element represents the total candies received by that person after the full distribution process completes.

The constraints are important:

  • candies can be as large as 10^9
  • num_people can be as large as 1000

The relatively small upper bound on num_people means storing the result array is trivial. However, the very large upper bound on candies suggests we should avoid unnecessarily expensive operations if possible.

Several edge cases are important to recognize immediately. If the number of candies is smaller than the next intended gift, the algorithm must correctly give only the remaining candies. If there is only one person, that person receives every candy regardless of the distribution sequence. Another subtle case occurs when the candies run out exactly after a full distribution step, because the algorithm must terminate cleanly without attempting another iteration.

Approaches

Brute Force Approach

The most direct solution is to simulate the process exactly as described in the problem statement.

We maintain:

  • A result array initialized with zeros
  • A variable representing the next gift amount
  • A pointer indicating which person should receive candies next

At each step:

  1. Determine how many candies can actually be given
  2. Add that amount to the current person
  3. Subtract it from the remaining candies
  4. Move to the next person cyclically
  5. Increase the gift amount by one

This approach is easy to understand because it mirrors the problem statement exactly. Every iteration corresponds to one distribution event.

The approach is correct because the simulation preserves the exact order and quantities required by the problem. Every candy distribution is performed according to the rules.

Although candies can be large, the number of distribution operations grows only until the cumulative sum exceeds candies. Since:

$$1 + 2 + 3 + \dots + k = \frac{k(k+1)}{2}$$

the number of iterations is approximately:

$$O(\sqrt{\text{candies}})$$

For candies = 10^9, this is still manageable.

Key Insight for the Optimal Approach

The important observation is that we never need to simulate individual candies, only distribution rounds.

Each iteration gives a predictable increasing amount:

$$1, 2, 3, 4, \dots$$

Instead of complicated mathematical derivations, we can efficiently simulate gift operations directly because the number of operations remains relatively small even for large inputs.

The simulation approach is already efficient enough for the problem constraints. The optimal solution therefore focuses on clean cyclic distribution with careful handling of the final partial gift.

Approach Time Complexity Space Complexity Notes
Brute Force $O(\text{candies})$ $O(n)$ Simulates candy distribution one candy at a time
Optimal $O(\sqrt{\text{candies}})$ $O(n)$ Simulates gift operations directly

Algorithm Walkthrough

  1. Initialize a result array of length num_people with all values set to zero.

This array stores the total candies each person receives throughout the process. 2. Initialize a variable current_gift to 1.

This variable tracks how many candies should be given during the next distribution step. 3. Initialize a variable person_index to 0.

This identifies which person currently receives candies. 4. Continue the process while there are candies remaining.

At every iteration, we determine how many candies can actually be distributed. 5. Compute the amount to give.

The intended gift is current_gift, but if there are fewer candies remaining than that amount, we give only the remaining candies:

$$\text{gift} = \min(\text{current_gift}, \text{candies})$$ 6. Add the gift to the current person's total.

Update:

$$\text{result[person_index]} += \text{gift}$$ 7. Subtract the distributed candies from the remaining total.

Update:

$$\text{candies} -= \text{gift}$$ 8. Move to the next person cyclically.

Since the row wraps around, we use modulo arithmetic:

$$\text{person_index} = (\text{person_index} + 1) \bmod \text{num_people}$$ 9. Increment the next intended gift amount.

Update:

$$\text{current_gift} += 1$$ 10. Once all candies are exhausted, return the result array.

Why it works

The algorithm maintains the invariant that every distribution step exactly matches the rules described in the problem statement. The current gift amount always increases by one after every operation, and the current person cycles correctly through the array. Using min(current_gift, candies) guarantees the final partial distribution is handled correctly without exceeding the available candies.

Python Solution

from typing import List

class Solution:
    def distributeCandies(self, candies: int, num_people: int) -> List[int]:
        result = [0] * num_people
        
        current_gift = 1
        person_index = 0
        
        while candies > 0:
            gift = min(current_gift, candies)
            
            result[person_index] += gift
            candies -= gift
            
            current_gift += 1
            person_index = (person_index + 1) % num_people
        
        return result

The implementation begins by creating the result array, where each index corresponds to one person in the row.

The variable current_gift tracks the next amount to distribute. It starts at 1 because the first distribution gives one candy.

The person_index variable identifies which person receives the current gift. After every distribution, modulo arithmetic wraps the index back to the beginning of the row when necessary.

Inside the loop, gift = min(current_gift, candies) is the key detail that correctly handles the final partial distribution. If fewer candies remain than the intended gift amount, the remaining candies are distributed instead.

After updating the result array and subtracting the distributed candies, the algorithm increments the intended gift amount and advances to the next person.

The loop terminates naturally once all candies have been distributed.

Go Solution

func distributeCandies(candies int, num_people int) []int {
    result := make([]int, num_people)

    currentGift := 1
    personIndex := 0

    for candies > 0 {
        gift := currentGift
        if candies < currentGift {
            gift = candies
        }

        result[personIndex] += gift
        candies -= gift

        currentGift++
        personIndex = (personIndex + 1) % num_people
    }

    return result
}

The Go implementation closely mirrors the Python solution. The primary difference is that Go does not provide a built in min function for integers, so the code uses an explicit conditional statement to determine the actual gift amount.

The result array is implemented as a slice using make([]int, num_people). Since Go slices are initialized with zero values automatically, no additional setup is needed.

Integer overflow is not a concern because the constraints fit safely within Go's standard integer range on LeetCode platforms.

Worked Examples

Example 1

Input:

candies = 7
num_people = 4

Initial state:

Step Gift Person Result Array Candies Left
Start - - [0,0,0,0] 7

Step by step execution:

Step Intended Gift Actual Gift Person Result Array Candies Left
1 1 1 0 [1,0,0,0] 6
2 2 2 1 [1,2,0,0] 4
3 3 3 2 [1,2,3,0] 1
4 4 1 3 [1,2,3,1] 0

Final answer:

[1,2,3,1]

Example 2

Input:

candies = 10
num_people = 3

Initial state:

Step Gift Person Result Array Candies Left
Start - - [0,0,0] 10

Step by step execution:

Step Intended Gift Actual Gift Person Result Array Candies Left
1 1 1 0 [1,0,0] 9
2 2 2 1 [1,2,0] 7
3 3 3 2 [1,2,3] 4
4 4 4 0 [5,2,3] 0

Final answer:

[5,2,3]

Complexity Analysis

Measure Complexity Explanation
Time $O(\sqrt{\text{candies}})$ Number of distribution operations grows with triangular numbers
Space $O(\text{num_people})$ Result array stores one value per person

The time complexity comes from the increasing distribution amounts. After k operations, the total candies distributed equals:

$1+2+3+\dots+k=\frac{k(k+1)}{2}$

To exhaust candies, the number of operations is approximately proportional to:

$$\sqrt{2 \times \text{candies}}$$

Therefore, the runtime is $O(\sqrt{\text{candies}})$.

The space complexity is $O(\text{num_people})$ because the algorithm stores only the output array and a few constant sized variables.

Test Cases

from typing import List

class Solution:
    def distributeCandies(self, candies: int, num_people: int) -> List[int]:
        result = [0] * num_people
        
        current_gift = 1
        person_index = 0
        
        while candies > 0:
            gift = min(current_gift, candies)
            
            result[person_index] += gift
            candies -= gift
            
            current_gift += 1
            person_index = (person_index + 1) % num_people
        
        return result

solution = Solution()

assert solution.distributeCandies(7, 4) == [1, 2, 3, 1]  # provided example 1
assert solution.distributeCandies(10, 3) == [5, 2, 3]  # provided example 2

assert solution.distributeCandies(1, 1) == [1]  # minimum input values
assert solution.distributeCandies(2, 1) == [2]  # single person receives everything
assert solution.distributeCandies(3, 2) == [1, 2]  # exact exhaustion after one round
assert solution.distributeCandies(4, 2) == [1, 3]  # partial final distribution
assert solution.distributeCandies(15, 4) == [6, 2, 3, 4]  # multiple cycles
assert solution.distributeCandies(20, 3) == [5, 7, 8]  # wraparound distribution
assert solution.distributeCandies(100, 5) == [18, 21, 24, 22, 15]  # larger input
assert solution.distributeCandies(1000000000, 1000) is not None  # stress test
Test Why
candies=7, num_people=4 Validates provided example with partial final gift
candies=10, num_people=3 Validates provided example with exact exhaustion
candies=1, num_people=1 Tests minimum constraints
candies=2, num_people=1 Ensures single person receives all candies
candies=3, num_people=2 Tests exact completion after full step
candies=4, num_people=2 Tests incomplete final distribution
candies=15, num_people=4 Verifies multiple cycles through people
candies=20, num_people=3 Tests repeated wraparound behavior
candies=100, num_people=5 Larger general correctness test
candies=1000000000, num_people=1000 Stress test for performance

Edge Cases

One important edge case occurs when there is only one person. In this situation, every distribution step targets the same individual. A buggy implementation might incorrectly attempt to rotate through nonexistent indices or mishandle modulo arithmetic. The implementation handles this naturally because (0 + 1) % 1 always evaluates to 0, so the single person continuously receives candies until none remain.

Another critical edge case happens when the remaining candies are fewer than the intended next gift amount. For example, if the next intended gift is 10 but only 3 candies remain, the algorithm must distribute exactly 3 candies and stop immediately. The use of min(current_gift, candies) guarantees this behavior and prevents negative candy counts.

A third important case occurs when candies run out exactly after a full distribution step. Some implementations accidentally continue into another iteration or increment variables incorrectly after exhaustion. This implementation avoids the issue because the loop condition checks candies > 0 before every iteration, so the algorithm terminates cleanly once all candies are distributed.