1103. Distribute Candies to People

EasyMathSimulation
Leetcode Link

Problem Description

In this problem, we have a certain number of candies that need to be distributed to num_people people arranged in a row. The distribution starts with the first person receiving one candy, the second person receiving two candies, and so on, increasing the count of candies by one for each subsequent person until the nth person receives n candies. After reaching the last person, the distribution continues from the first person again, but this time each person gets one more candy than the previous cycle (so the first person now gets n+1 candies, the second gets n+2, and so on). This process repeats until we run out of candies. If there are not enough candies to give the next person in the sequence their "full" amount, they receive the remaining candies, and the distribution ends.

The goal is to return an array of length num_people, with each element representing the total number of candies that each person receives at the end of the distribution process.

Intuition

To solve this problem, we want to simulate the described candy distribution process. We keep handing out candies until we have none left. Each person gets a certain number of candies based on the round of distribution we are in. In the first round, person 1 gets 1 candy, person 2 gets 2 candies, and so on. Once we reach num_people, we wrap around and start from person 1 again, increasing the amount of candy given out by num_people each round.

The solution involves iterating over the people in a loop and incrementing the number of candies each person gets by the distribution rule given. We maintain a counter i to keep track of how many candies have been given out so far, and a list ans to store the total candies for each person.

With each person's turn, we give out the number of candies equal to the counter i + 1, but if we have fewer candies left than i + 1, we give out all the remaining candies. After that, we update the total number of candies left by subtracting the number given out. If the candies finish during someone's turn, we stop the distribution and return our ans list to show the final distribution of candies.

The intuition is to replicate the physical process of handing out the candies in a loop, ensuring that conditions such as running out of candies are properly handled.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which two pointer technique does Quick Sort use?

Solution Approach

The solution to this problem uses a simple iterative approach as our algorithm. Here are the steps and the reasoning in detail:

  1. Initialize the Answer List: We start by initializing an array ans of length num_people with all elements set to 0. This array will be used to keep track of the number of candies each person receives.

  2. Starting the Distribution: We need to keep track of two things - the index of the person to whom we're currently giving candies, and the number of candies we're currently handing out. We start the distribution by setting a counter i to 0, which will increase with each iteration to represent the amount of candy to give.

  3. Iterative Distribution: We use a while loop to continue distributing candies until we run out (candies > 0). During each iteration of the loop:

    • Compute i % num_people to find the index of the current person. This ensures that after the last person, we start again from the first person.
    • Determine the number of candies to give to the current person. We use min(candies, i + 1) to decide this amount because we either give i + 1 candies or the remaining candies if we have less than i + 1.
    • Subtract the number of distributed candies from candies.
    • Increment i by 1 to update the count for the next iteration.

  4. Updating Answer List: In each iteration, update ans[i % num_people] with the number of candies distributed in that iteration.

  5. Handling Remaining Candies: If we deplete our supply of candies, we give out the remaining candies to the last person. This is built into the allocation step with min(candies, i + 1).

  6. Returning the Final Distribution: Once the loop ends (no more candies are left), we exit the loop. The array ans now contains the total number of candies received by each person, which we return as the final answer.

This problem does not require any complex data structures or patterns. The concept is straightforward and only uses basic array manipulation to achieve the goal. It focuses on handling the loop correctly and ensuring that the distribution of candies is done according to the specified rules.

1class Solution:
2    def distributeCandies(self, candies: int, num_people: int) -> List[int]:
3        ans = [0] * num_people  # Initialize the answer list
4        i = 0                   # Counter for the distribution process
5        # Distribute candies until we run out
6        while candies:          
7            # Give out min(candies, i + 1) candies to the (i % num_people)th person
8            ans[i % num_people] += min(candies, i + 1) 
9            candies -= min(candies, i + 1) # Subtract the candies given from the total
10            i += 1  # Move to the next person
11
12        return ans  # Return the final distribution

The solution makes effective use of modulo operation to cycle through the indices repeatedly while the while loop condition ensures that the distribution halts at the right time.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Example Walkthrough

Let's use a small example to illustrate the solution approach.

Suppose we have candies = 7 and num_people = 4.

We want to distribute these candies across 4 people as described. Let's walk through the process using the provided algorithm.

  1. Initialize the Answer List:
    • ans = [0, 0, 0, 0]
  2. Starting the Distribution:
    • candies = 7
    • Distribution counter i = 0
  3. Iterative Distribution:
    1. During the first iteration (i = 0):
      • Current person index: 0 % 4 = 0 (first person)
      • Candies to give out: min(7, 0 + 1) = 1
      • Remaining candies: 7 - 1 = 6
      • Updated ans list: [1, 0, 0, 0]
      • Increment i to 1
    2. In the second iteration (i = 1):
      • Current person index: 1 % 4 = 1 (second person)
      • Candies to give out: min(6, 1 + 1) = 2
      • Remaining candies: 6 - 2 = 4
      • Updated ans list: [1, 2, 0, 0]
      • Increment i to 2
    3. In the third iteration (i = 2):
      • Current person index: 2 % 4 = 2 (third person)
      • Candies to give out: min(4, 2 + 1) = 3
      • Remaining candies: 4 - 3 = 1
      • Updated ans list: [1, 2, 3, 0]
      • Increment i to 3
    4. In the fourth iteration (i = 3):
      • Current person index: 3 % 4 = 3 (fourth person)
      • Candies to give out: min(1, 3 + 1) = 1
      • Remaining candies: 1 - 1 = 0 (no more candies)
      • Updated ans list: [1, 2, 3, 1]
      • Candies are now depleted, we stop the distribution.
  4. Return the Final Distribution:
    • The final ans list is [1, 2, 3, 1].

Each element in the ans list represents the total number of candies each person receives after the distribution is done. The algorithm successfully mimics the handing out of candies until there are no more left, while following the rules set out in the problem description.

Solution Implementation

1from typing import List
2
3class Solution:
4    def distributeCandies(self, candies: int, num_people: int) -> List[int]:
5        # Initialize a list to hold the number of candies each person will receive
6        distribution = [0] * num_people
7        # Initialize an index variable to distribute candies to the people in order
8        index = 0
9      
10        # Continue distribution until there are no more candies left
11        while candies > 0:
12            # Calculate the number of candies to give: either 1 more than the current index
13            # or the remaining candies if fewer than that number remain
14            give = min(candies, index + 1)
15            # Distribute the candies to the current person
16            distribution[index % num_people] += give
17            # Subtract the number of candies given from the remaining total
18            candies -= give
19            # Move to the next person for the next round of distribution
20            index += 1
21          
22        # Return the final distribution
23        return distribution
24
1class Solution {
2    public int[] distributeCandies(int candies, int numPeople) {
3        // Initialize the answer array with the size equal to numPeople. 
4        // All elements are initialized to 0.
5        int[] distribution = new int[numPeople];
6      
7        // Initialize the index for the current person
8        // and the amount to give out to the current person
9        int index = 0;
10        int currentCandyAmount = 1;
11      
12        // Use a loop to distribute the candies until all candies are distributed
13        while (candies > 0) {
14            // Calculate the index for the current distribution round
15            // It cycles back to 0 when it reaches numPeople
16            int personIndex = index % numPeople;
17          
18            // Determine the number of candies to give out
19            // It is the minimum of either the remaining candies or the current amount
20            int candiesToGive = Math.min(candies, currentCandyAmount);
21          
22            // Update the candies count for the current person
23            distribution[personIndex] += candiesToGive;
24          
25            // Subtract the candies given out from the total count of remaining candies
26            candies -= candiesToGive;
27          
28            // Move to the next person and increment the candy amount
29            index++;
30            currentCandyAmount++;
31        }
32      
33        // Return the distribution result
34        return distribution;
35    }
36}
37
1#include <vector>
2#include <algorithm> // for std::min function
3
4class Solution {
5public:
6    /**
7     * Distributes candies among people in a loop.
8     *
9     * @param candies Number of candies to distribute.
10     * @param num_people Number of people to distribute the candies to.
11     * @return A vector<int> containing the distribution of candies.
12     */
13    vector<int> distributeCandies(int candies, int num_people) {
14        vector<int> distribution(num_people, 0); // Create a vector with num_people elements, all initialized to 0
15        int i = 0; // Initialize a counter to track the number of candies given
16
17        // Continue distributing candies until none are left
18        while (candies > 0) {
19            // Calculate the index of the current person and the amount of candies to give
20            int index = i % num_people;
21            int give = std::min(candies, i + 1); // The number of candies to give is the lesser of the remaining candies and the current count
22
23            distribution[index] += give; // Distribute the candies to the current person
24            candies -= give; // Decrease the total candy count
25
26            ++i; // Move to the next candy count
27        }
28
29        return distribution; // Return the final distribution
30    }
31};
32
1// Function to distribute candies among people in a way that the ith allocation
2// increases by 1 candy
3function distributeCandies(candies: number, numPeople: number): number[] {
4    // Initialize an answer array to hold the number of candies for each person,
5    // starting with zero candies for each person
6    const distribution: number[] = new Array(numPeople).fill(0);
7  
8    // Variable to track the current distribution round
9    let currentDistribution = 0;
10
11    // Continue distributing candies until none are left
12    while (candies > 0) {
13        // Calculate the current person's index by using modulo with numPeople.
14        // This ensures we loop over the array repeatedly
15        const currentIndex = currentDistribution % numPeople;
16      
17        // Determine the number of candies to give in this round. It is the minimum
18        // of the remaining candies and the current distribution amount (1-indexed)
19        const candiesToGive = Math.min(candies, currentDistribution + 1);
20      
21        // Update the distribution array for the current person
22        distribution[currentIndex] += candiesToGive;
23      
24        // Subtract the given candies from the total remaining candies
25        candies -= candiesToGive;
26
27        // Move on to the next round of distribution
28        currentDistribution++;
29    }
30  
31    // Return the final distribution of candies
32    return distribution;
33}
34
Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Time and Space Complexity

The time complexity of the given code can be determined by the while loop, which continues until all candies are distributed. In each iteration of the loop, i is incremented by 1, and the amount of candies distributed is also incremented by 1 until all candies are exhausted. This forms an arithmetic sequence from 1 to n where n is the turn where the candies run out. The total number of candies distributed by this sequence can be represented by the sum of the first n natural numbers formula n*(n+1)/2. So the time complexity is governed by the smallest n such that n*(n+1)/2 >= candies. Therefore, the time complexity is O(sqrt(candies)) because we need to find an n such that n^2 is asymptotically equal to the total number of candies.

The space complexity of the code is determined by the list ans that has a size equal to num_people. Since the size of this list does not change and does not depend on the number of candies, the space complexity is O(num_people), which is the space required to store the final distribution of the candies among the people.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫