Scale Engineer

Distribute Candies to People

Easy
#1044Time: O(sqrt(candies)). Let K be the number of turns. The total candies distributed is the sum of the first K integers, which is `K*(K+1)/2`. This sum is approximately equal to the initial `candies`. Therefore, `K^2` is proportional to `candies`, and `K` (the number of loop iterations) is proportional to `sqrt(candies)`.Space: O(num_people) to store the result array.
Patterns
Math

Prompt

We distribute some number of candies, to a row of n = num_people people in the following way:

We then give 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 go back to the start of the row, giving n + 1 candies to the first person, n + 2 candies to the second person, and so on until we give 2 * n candies to the last person.

This process repeats (with us giving one more candy each time, and moving to the start of the row after we reach the end) until we run out of candies.  The last person will receive all of our remaining candies (not necessarily one more than the previous gift).

Return an array (of length num_people and sum candies) that represents the final distribution of candies.

 

Example 1:

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

 

Constraints:

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. We maintain the current number of candies to give and the index of the person to receive them. In a loop, we distribute candies turn by turn until we run out.

Algorithm

  • Create a result array ans of size num_people and initialize all its elements to 0.
  • Initialize give = 1 to track the number of candies for the current turn.
  • Initialize i = 0 as the index for the current person.
  • Start a loop that continues as long as candies > 0.
  • Inside the loop, determine the number of candies to give in this turn: candiesToGive = min(candies, give).
  • Add candiesToGive to ans[i].
  • Decrease candies by candiesToGive.
  • Increment give by 1 for the next turn.
  • Update the person index: i = (i + 1) % num_people.
  • After the loop terminates, return the ans array.

Walkthrough

This method follows the problem description literally. We initialize an integer array ans of size num_people with all elements as 0. We also use a variable give to track the number of candies to be distributed in the current turn, starting from 1, and an index i to point to the current person in the row, starting from 0.

We loop as long as we have candies left. In each iteration, we check if the remaining candies are enough for the current turn. If candies is less than give, the current person receives all the remaining candies. Otherwise, they receive give candies. We update the person's total in the ans array and decrement the total candies. Then, we prepare for the next turn by incrementing give and moving to the next person by updating the index i (wrapping around to the start of the row if necessary).

class Solution {    public int[] distributeCandies(int candies, int num_people) {        int[] ans = new int[num_people];        int give = 1;        int i = 0;        while (candies > 0) {            int candiesToGive = Math.min(candies, give);            ans[i] += candiesToGive;            candies -= candiesToGive;            give++;            i = (i + 1) % num_people;        }        return ans;    }}

Complexity

Time

O(sqrt(candies)). Let K be the number of turns. The total candies distributed is the sum of the first K integers, which is `K*(K+1)/2`. This sum is approximately equal to the initial `candies`. Therefore, `K^2` is proportional to `candies`, and `K` (the number of loop iterations) is proportional to `sqrt(candies)`.

Space

O(num_people) to store the result array.

Trade-offs

Pros

  • Simple to understand and implement.

  • Works correctly for all valid inputs.

Cons

  • Can be slow if candies is very large (e.g., close to 10^9), as the number of iterations would be around 31,622. This might lead to a 'Time Limit Exceeded' error on some platforms, although it's generally acceptable.

Solutions

class Solution {public  int[] distributeCandies(int candies, int num_people) {    int[] ans = new int[num_people];    for (int i = 0; candies > 0; ++i) {      ans[i % num_people] += Math.min(candies, i + 1);      candies -= Math.min(candies, i + 1);    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem