algoadvance

Leetcode 1103. Distribute Candies to People

Problem Statement

You are given candies number of candies that you need to distribute to num_people people. The task is to distribute the candies in the following way:

• You start by giving 1 candy to the first person, 2 candies to the second person, and so on until you give i candies to the i-th person.
• After you have given to the num_people-th person, you start again from the first person and continue giving candies.

You need to return an array that represents the number of candies each person gets.

Clarifying Questions

1. What happens if we run out of candies before completely fulfilling a person’s right to candies?
   • If there are fewer candies remaining than required for the next distribution, give all remaining candies to that person.
2. What should be the format of the output?
   • Return an array containing the number of candies each person receives.

Strategy

1. Initialization:
   • Create an array result of length equal to num_people, initialized to 0.
   • Declare a variable current_candy to keep track of the number of candies to distribute on each turn.
2. Distribution Loop:
   • Use a loop to distribute candies until all candies are exhausted.
   • For each iteration, update the corresponding person’s count.
   • If the remaining candies are fewer than current_candy, distribute all remaining candies and exit.
3. Index Management:
   • Use a modulo operation to cycle through the people array continuously.

Code

#include <vector>
#include <iostream>
using namespace std;

vector<int> distributeCandies(int candies, int num_people) {
    vector<int> result(num_people, 0);  // Initialize result array with 0s
    int current_candy = 1;  // Start with 1 candy to distribute
    int index = 0;  // Start with the first person

    while (candies > 0) {
        if (candies < current_candy) {
            result[index] += candies;  // If the remaining candies are less than current_candy
            break;  // Exhaust all candies
        } else {
            result[index] += current_candy;
        }
        
        candies -= current_candy;  // Decrease the remaining candies
        current_candy++;  // Increment the candies to distribute next time
        index = (index + 1) % num_people;  // Move to the next person cyclically
    }

    return result;
}

// Driver function for testing purposes
int main() {
    int candies = 7;
    int num_people = 4;
    vector<int> result = distributeCandies(candies, num_people);
    
    for (int candy : result) {
        cout << candy << " ";
    }
    cout << endl;
    return 0;
}

Time Complexity

• The loop runs as long as there are candies left, and current_candy increases by 1 each iteration. The sum of the first n integers is (\frac{n(n + 1)}{2}). Therefore, the number of iterations is approximately (\sqrt{2 \times \text{candies}}). Thus, the time complexity is (O(\sqrt{\text{candies}})).

Space Complexity

• We only use an extra array of size num_people, so the space complexity is (O(\text{num_people})).

This code provides an efficient and clear approach to solving the problem by iteratively distributing candies in the specified manner.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?