#1103

Easy

LeetCode Problem Workspace

Distribute Candies to People

Distribute candies to people in a way that follows a mathematical pattern, ensuring the distribution is correct.

Problem Statement

We are tasked with distributing a given number of candies to a row of people, following a specific order. Starting from the first person, give 1 candy to the first person, 2 to the second, 3 to the third, and so on, until each person gets candies in increasing amounts. Once the last person receives their candies, the cycle repeats, but with the next person getting one more candy than the last cycle.

For example, if there are 7 candies and 4 people, you start by giving 1 candy to the first person, 2 to the second, 3 to the third, and 1 candy again to the fourth person, completing the cycle with remaining candies. This process continues until all candies are distributed. Your goal is to return an array representing the final distribution of candies to each person.

Examples

Example 1

Input: candies = 7, num_people = 4

Output: [1,2,3,1]

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]

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 Approach

Simulate Candy Distribution

Start by initializing an array with zeros to represent the number of candies each person gets. Loop through the people and distribute candies incrementally, starting from 1 candy for the first person, and then distributing candies in increasing order. When you reach the end of the row, repeat the cycle, but increment the number of candies given.

Handle Remaining Candies Efficiently

During each cycle, the number of candies decreases. When candies are fewer than the number required for the full cycle, give as many as possible, and adjust the next distribution accordingly. The simulation should continue until all candies are assigned.

Optimize for Large Inputs

Given that the problem allows up to 10^9 candies, it is important to optimize the solution. You can avoid redundant calculations by skipping full cycles if the remaining candies are less than the number required for a complete cycle.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the number of candies and people. In the worst case, the solution needs to perform multiple passes over the people, with a time complexity roughly proportional to the number of candies divided by the number of people. Space complexity is O(n), where n is the number of people, as the solution stores the candy distribution for each person.

What Interviewers Usually Probe

Candidate should focus on simulating the candy distribution step by step.
Watch for optimization efforts, especially when the candy count is very high.
Check if the candidate correctly handles cases with fewer candies than required for a full cycle.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the cyclical distribution process and giving candies in the wrong order.
Failing to properly handle the case where remaining candies are fewer than needed for a full cycle.
Inefficient solutions that do not scale well with large inputs, like using brute force to simulate every candy distribution.

Follow-up variants

Modify the distribution pattern, for example, skipping the increment for certain people.
Adjust the problem by giving candies to people based on a fixed pattern of skips.
Consider a different distribution order or a priority queue system for the people receiving candies.

FAQ

How does the candy distribution work in this problem?

Candies are distributed in an increasing manner, starting from 1 candy for the first person and continuing in a loop until all candies are distributed.

What happens if there are fewer candies than needed for a full cycle?

If there are fewer candies left than the number required for a full cycle, you give as many as possible and adjust the remaining distribution accordingly.

What is the time complexity of the solution?

The time complexity depends on the number of candies and people. The worst-case time complexity is proportional to the number of candies divided by the number of people.

How can I optimize the solution for large inputs?

You can optimize by skipping full cycles if the remaining candies are fewer than the number needed for a complete cycle.

Can the candy distribution pattern be modified?

Yes, you can modify the distribution pattern, such as adjusting the increment for each cycle or using a different order for candy allocation.

terminal

Solution

Solution 1: Simulation

We can directly simulate the process of each person receiving candies, following the rules described in the problem.

1

2

3

4

5

6

7

8

9

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

Continue Practicing

#1041 robot bounded in circle #1006 clumsy factorial #1252 cells with odd values in a matrix