Distribute Candies to People

Easy
487.

Distribute Candies to People

Distribute Candies to People is an easy coding problem on arrays, math and simulation, asked in Amazon interviews.

You have candies sweets to hand out to numPeople people standing in a row.

Go down the row giving 1 sweet to the first person, 2 to the second, and so on up to numPeople sweets to the last. Then start again from the first person, giving numPeople + 1, numPeople + 2, … and keep looping.

When fewer sweets remain than the next person is owed, that person gets all the remainder and the process stops. Return the final count each person holds.

Example 1

Input
candies = 7, numPeople = 4
Output
[1,2,3,1]
Explanation
1, 2, 3 are given in full; only 1 sweet is left for the fourth person.

Example 2

Input
candies = 10, numPeople = 3
Output
[5,2,3]
Explanation
Round one gives 1,2,3; then the first person takes the remaining 4.

Example 3

Input
candies = 1, numPeople = 1
Output
[1]

Constraints

  • 1 <= candies <= 1000000000
  • 1 <= numPeople <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} candies
 * @param {number} numPeople
 * @return {number[]}
 */
var distributeCandies = function(candies, numPeople) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Distribute Candies to People — Problem & Solution

Distribute Candies to People solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Distribute Candies to People is an easy coding problem on arrays, math and simulation, asked in Amazon interviews.

  • Difficulty: Easy
  • Topics: Arrays, Math, Simulation
  • Asked at: Amazon
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You have candies sweets to hand out to numPeople people standing in a row.

Go down the row giving 1 sweet to the first person, 2 to the second, and so on up to numPeople sweets to the last. Then start again from the first person, giving numPeople + 1, numPeople + 2, … and keep looping.

When fewer sweets remain than the next person is owed, that person gets all the remainder and the process stops. Return the final count each person holds.

Example 1

Input: candies = 7, numPeople = 4
Output: [1,2,3,1]
Explanation: 1, 2, 3 are given in full; only 1 sweet is left for the fourth person.

Example 2

Input: candies = 10, numPeople = 3
Output: [5,2,3]
Explanation: Round one gives 1,2,3; then the first person takes the remaining 4.

Example 3

Input: candies = 1, numPeople = 1
Output: [1]

Constraints

  • 1 <= candies <= 1000000000
  • 1 <= numPeople <= 1000

Hints for Distribute Candies to People

  1. Hint 1

    The loop runs until the sweets are gone — how many rounds is that at most?

  2. Hint 2

    The k-th handout is k + 1 sweets, so after m handouts you have spent m(m+1)/2. That caps the loop at about sqrt(2 · candies) steps.

  3. Hint 3

    Use min(owed, remaining) for each handout so the final partial gift is handled by the same line of code.

How to solve Distribute Candies to People

Straight simulation is fast enough: the handouts grow linearly, so the total number of them is on the order of sqrt(2 · candies) — about 45,000 even at the maximum.

Approach

  1. Allocate an array of numPeople zeros.
  2. Track give (the amount owed on this handout, starting at 1) and i (the handout index).
  3. Each step, hand out min(give, remaining) to person i % numPeople, subtract it from the remainder, then increment both counters.
  4. Stop when nothing remains and return the array.

Why it works

Handing out min(give, remaining) collapses the "give everything that is left" rule into the ordinary case, so the loop needs no special final branch. The loop terminates because every iteration removes at least one sweet.

Complexity

  • Time — O(sqrt(candies) + numPeople)
  • Space — O(numPeople)

Pitfalls

  • Giving give unconditionally overshoots and leaves a negative remainder.
  • Resetting give to 1 at the start of each round is wrong — it keeps growing across rounds.
  • Indexing must wrap with % numPeople, not stop at the end of the row.

Reference solution

Python

from typing import List

def distributeCandies(candies: int, numPeople: int) -> List[int]:
    out = [0] * numPeople
    give = 1
    i = 0
    while candies > 0:
        g = give if give < candies else candies
        out[i % numPeople] += g
        candies -= g
        give += 1
        i += 1
    return out

Java

public static int[] distributeCandies(int candies, int numPeople) {
    int[] out = new int[numPeople];
    long give = 1;
    int i = 0;
    while (candies > 0) {
        long g = Math.min(give, (long) candies);
        out[i % numPeople] += (int) g;
        candies -= (int) g;
        give++;
        i++;
    }
    return out;
}

C++

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

JavaScript

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

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays