Distribute Candies to People

easy array simulation math

Problem

We distribute some number of candies to a row of num_people people in the following way. We give 1 candy to the first person, 2 to the second, and so on up to num_people candies to the last person. Then we go back to the start, giving num_people + 1 candies to the first person, num_people + 2 to the second, and so on. This continues, each turn giving one more candy than the last, wrapping around as needed, until we run out of candies. The last person to receive candies gets all the remaining candies, even if it is fewer than what they would otherwise be given. Return an array of length num_people showing the final count each person holds.

Inputcandies = 7, num_people = 4

Output[1, 2, 3, 1]

Hand out 1, 2, 3, then only 1 candy remains for person 4 (would be 4, but capped at 1).

candies

num_people

def distribute_candies(candies, num_people):
    res = [0] * num_people
    give = 1
    i = 0
    while candies > 0:
        amount = min(give, candies)
        res[i % num_people] += amount
        candies -= amount
        give += 1
        i += 1
    return res

function distributeCandies(candies, numPeople) {
  const res = new Array(numPeople).fill(0);
  let give = 1, i = 0;
  while (candies > 0) {
    const amount = Math.min(give, candies);
    res[i % numPeople] += amount;
    candies -= amount;
    give += 1;
    i += 1;
  }
  return res;
}

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

vector<int> distributeCandies(int candies, int numPeople) {
    vector<int> res(numPeople, 0);
    int give = 1, i = 0;
    while (candies > 0) {
        int amount = min(give, candies);
        res[i % numPeople] += amount;
        candies -= amount;
        give += 1;
        i += 1;
    }
    return res;
}

Explanation

The cleanest way to solve this is to simply act out the handing-out process exactly as described, one turn at a time, until the candy runs out. No formula needed — we just keep a running count.

We track three things: res (how much each person holds), give (how many candies this turn should hand out, starting at 1 and growing by one each turn), and i (which turn we are on). The person who gets candy is i % num_people, which makes the line wrap back around to the start automatically.

On each turn we give amount = min(give, candies). The min is the important guard: if fewer candies remain than we would normally give, the last person just gets whatever is left. We add that to their total, subtract it from the remaining candies, and bump give and i.

Example: candies = 7, num_people = 4. Turn 1 gives 1 to person 0, turn 2 gives 2 to person 1, turn 3 gives 3 to person 2 (now 1 candy left), turn 4 would give 4 to person 3 but only 1 remains, so they get 1. Result: [1, 2, 3, 1].

Since the amounts grow each turn, the candy is used up quickly, so the number of turns stays small relative to the candy count.

Time: O(√candies) Space: O(num_people)