#1103
Distribute Candies to People
EasyMathSimulationArithmetic SeriesSimulation
Approaches
Brute ForceOptimal
Complexity Comparison
| Brute Force | Optimal Solution★ | |
|---|---|---|
| Time | O(n²) | O(n) |
| Space | O(1) | O(n) |
💡
Intuition
Time O(n)Space O(n)
Instead of simulating each distribution, we can calculate how many full rounds we can complete and then distribute the remaining candies more efficiently. This reduces the number of iterations significantly.
⚙️
Algorithm
3 steps- 1Step 1: Calculate the total number of candies needed for k full rounds, where k is the maximum number of complete rounds we can distribute.
- 2Step 2: Use the formula for the sum of an arithmetic series to find the total candies needed for k rounds: total_candies = k * (k + 1) / 2 * num_people.
- 3Step 3: Determine how many candies are left after distributing to k rounds and distribute them among the people.
solution.py14 lines
1def distributeCandies(candies, num_people):
2 distribution = [0] * num_people
3 k = int(((8 * candies + 1) ** 0.5 - 1) // 2)
4 total_candies = k * (k + 1) // 2 * num_people
5 for i in range(num_people):
6 distribution[i] = (k * (k + 1)) // 2 + (k // num_people) + (1 if i < k % num_people else 0)
7 remaining_candies = candies - total_candies
8 for i in range(num_people):
9 if remaining_candies <= 0:
10 break
11 give = min(remaining_candies, i + 1 + k * num_people)
12 distribution[i] += give
13 remaining_candies -= give
14 return distributionℹ
Complexity note: The time complexity is O(n) because we efficiently calculate the distribution without simulating each candy distribution, and we only iterate through the number of people once.
- 1Understanding how to calculate rounds can save time and effort in distribution problems.
- 2Recognizing patterns in distribution can help optimize the solution.
Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.