Domain 1EasyCORE

Distribute Candies to People

The problem requires distributing a given number of candies to a row of people in a specific pattern. 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 last person. Then, we repeat this process, starting again from the first person but increasing the number of candies given each time by 1. This continues until all candies are distributed. The final distribution should be returned as an array where each element represents the total number of candies received by that person.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#**FAANG asked:** 0

1103. Distribute Candies to People

Model: qwen2.5-coder:14b
Topics:
FAANG asked: 0
Acceptance rate: 63.4%


Problem Breakdown

The problem requires distributing a given number of candies to a row of people in a specific pattern. 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 last person. Then, we repeat this process, starting again from the first person but increasing the number of candies given each time by 1. This continues until all candies are distributed. The final distribution should be returned as an array where each element represents the total number of candies received by that person.

Inputs:

  • candies: An integer representing the total number of candies to distribute.
  • num_people: An integer representing the number of people in the row.

Outputs:

  • An array of length num_people where each element is the total number of candies received by that person.

Implicit Constraints or Tricky Edge Cases:

  • If candies is less than the sum of the first n natural numbers, we need to handle the case where the last person receives fewer candies than expected.
  • The distribution should be as fair as possible given the constraints.

Intuition

A brute-force approach would involve simulating the entire process of distributing candies one by one until all are distributed. This approach is inefficient because it has a time complexity of O(candies), which can be very high given the upper limit of candies being (10^9).

The key insight to improve this is to recognize that we can distribute candies in complete rounds where each person receives an increasing number of candies. After completing these rounds, any remaining candies can be distributed directly to the people until they run out.

Approach

  1. Initialize the Result Array: Create an array result of length num_people initialized to 0.
  2. Determine Complete Rounds: Calculate how many complete rounds of distribution can be made using the formula for the sum of the first k natural numbers: ( \frac{k(k+1)}{2} ). Find the largest k such that this sum is less than or equal to candies.
  3. Distribute Candies in Complete Rounds: For each complete round, distribute candies according to the pattern described.
  4. Distribute Remaining Candies: After completing all possible full rounds, distribute any remaining candies directly to the people until they run out.

Complexity Analysis

  • Time Complexity: (O(\sqrt{candies})) because we are finding the largest k such that the sum of the first k natural numbers is less than or equal to candies. This involves iterating up to (\sqrt{2 \times candies}).
  • Space Complexity: (O(num_people)) for storing the result array.

Solution

def distributeCandies(candies, num_people):
    result = [0] * num_people
    k = 0
    
    # Find the largest k such that (k * (k + 1)) // 2 <= candies
    while (k * (k + 1)) // 2 <= candies:
        for i in range(num_people):
            if candies == 0:
                break
            result[i] += min(candies, k * num_people + i + 1)
            candies -= (k * num_people + i + 1)
        k += 1
    
    return result

Edge Cases Handled

  • Small Number of Candies: If candies is less than the sum of the first n natural numbers, the last person will receive fewer candies than expected.
  • Single Person: If num_people is 1, all candies are given to that single person.
  • All Candies Distributed in One Round: If candies is exactly equal to the sum of the first n natural numbers for some k, the distribution will be complete after one round.