Distribute Candies to People

Problem Statement

The task is to distribute a specific number of candies among num_people in a structurally defined manner. Starting with the first person, we distribute increasing amounts of candies down the line—one more candy than the last person received. When we reach the last person, the distribution cycle starts again from the first person but continues the increment from the last cycle's end.

The sequence of distribution continues until there are no more candies left to distribute. If it is the turn of a person to get candies, but insufficient candies remain to follow the expected increment, that person receives all the remaining candies, potentially breaking the sequence of increments for the last distribution.

This prompt requires the return of an array indicating how many candies each person has received after all candies have been distributed. The length of the resulting array is num_people, and the sum of all its elements equals the total candies initially available.

Examples

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

Approach and Intuition

• The process essentially forms a simulation of distributing candies in rounds, where each member gets incrementally more until supplies run out.
• Each person in the cycle sequentially receives one more candy than the last, with cycles resetting to the first person after the last one receives their portion. In the next round, where we loop back to the first individual again, the sequence continues from the last number of candies plus one.

Now, let's step through how we might approach solving the problem with an example input:

1. Initialization:

   • Create an array of zeroes with size equal to num_people to hold the count of candies each person receives.

2. Iteratively Distributing Candies:

   • Use a loop to go through each person starting from the first to the last.
   • If it's the turn of the i-th (0-indexed) person, increase their candies based on the round. In round 1, person 1 gets 1 hamdy, in round 2 person 1 gets n + 1 candies (where n is the number of people).
   • If during any person's turn there aren't enough candies left to give them the expected amount (e.g., person is supposed to get 10 candies, but only 7 are remaining), give them all the remaining candies and end the distribution.

3. Handling Remaining Candies While Distributing:

   • Check at each step if the candies left are less than what the next person should get.
   • Assign the remainder to the current person and end the loop as all candies have been distributed.

This method ensures that the candies are distributed in line with the stipulated rules and that the process is both efficient and accurate, taking care of varying numbers of people and candies systematically.

Solutions

class Solution {
  public int[] distributeCandy(int totalCandies, int peopleCount) {
    int num = peopleCount;
    int k = (int)(Math.sqrt(2 * totalCandies + 0.25) - 0.5);
    int left = (int)(totalCandies - (k + 1) * k * 0.5);
    int fullRows = k / num, extra = k % num;

    int[] result = new int[num];
    for(int j = 0; j < num; ++j) {
      result[j] = (j + 1) * fullRows + (int)(fullRows * (fullRows - 1) * 0.5) * num;
      if (j < extra) result[j] += j + 1 + fullRows * num;
    }
    result[extra] += left;
    return result;
  }
}