Leetcode – Distribute Candies to People Solution

The “Distribute Candies to People” problem is a classic coding interview question that challenges your understanding of array manipulation, mathematics, and iteration techniques. In this in-depth article, we will explore various ways to tackle this problem, from brute-force solutions to more optimized algorithms. Alongside, we’ll examine the time and space complexities of each approach.

Problem Description

Here’s the problem description as given on Leetcode:

We distribute some number of candies to a row of n = num_people people in the following way:

We then give 1 candy to the first person, 2 candies to the second person, and so on until we give n candies to the last person.

Then, we go back to the start of the row, giving n + 1 candies to the first person, n + 2 candies to the second person, and so on until we give 2 * n candies to the last person.

This process repeats (with us giving one more candy each time, and moving to the start of the row after we reach the end) until we run out of candies. The last person will receive all of our remaining candies (not necessarily one more than the previous gift).

Return an array (of length num_people and sum candies) that represents the final distribution of candies.

Example:

Input: candies = 7, num_people = 4
Output: [1,2,3,1]

Brute-Force Approach

A straightforward approach to solve this problem is to iterate through the people and distribute the candies one by one according to the pattern specified.

Python Implementation:

def distributeCandies(candies, num_people):
    result = [0] * num_people
    i = 0
    candy_to_give = 1
    
    while candies > 0:
        result[i % num_people] += min(candy_to_give, candies)
        candies -= candy_to_give
        candy_to_give += 1
        i += 1
    
    return result

Time Complexity:

The time complexity is O(n), where n is the total number of candies.

Space Complexity:

The space complexity is O(k), where k is the number of people, which is used for the result array.

Mathematical Approach

By closely examining the problem, you’ll find that the series of candies given to each person forms an arithmetic series. We can solve this by finding out how many complete rounds of distribution can be made and then handling the remaining candies.

To find the number of complete rounds, we use the equation for the sum of the first n natural numbers,

where S is the total number of candies and n is the total number of complete rounds for one person.

Python Implementation:

def distributeCandies(candies, num_people):
    result = [0] * num_people
    
    # Calculate number of complete rounds
    n = int(((8 * candies + 1) ** 0.5 - 1) / 2)
    complete_rounds = n // num_people
    remaining = n % num_people
    
    for i in range(num_people):
        # Full rounds
        result[i] += (i + 1 + i + 1 + (complete_rounds - 1) * num_people) * complete_rounds // 2
        
        # Remaining
        if i < remaining:
            result[i] += i + 1 + complete_rounds * num_people
    
    # Add the remaining candies
    result[remaining] += candies - n * (n + 1) // 2
    
    return result

Time Complexity:

The time complexity is O(k), where k is the number of people.

Space Complexity:

The space complexity is O(k) for storing the result array.

Using itertools.cycle()

Python’s itertools.cycle() provides a convenient way to iterate over the list in a cyclical fashion.

Python Implementation:

from itertools import cycle

def distributeCandies(candies, num_people):
    result = [0] * num_people
    for i, c in zip(cycle(range(num_people)), range(1, candies + 1)):
        give = min(candies, c)
        result[i] += give
        candies -= give
        if candies == 0:
            break
    return result

Time Complexity:

The time complexity is O(n).

Space Complexity:

The space complexity is O(k).

Conclusion

The “Distribute Candies to People” problem provides an excellent exercise for understanding array manipulation and arithmetic sequences. While the brute-force approach is simple to implement, it lacks the performance that other optimized approaches offer.

The mathematical approach significantly improves the time complexity to O(k), making it the most optimized solution in terms of time complexity. On the other hand, using itertools.cycle() allows for more Pythonic and readable code while maintaining decent performance.