Jobs

Interviews

Discussions

Distribute Candies Among Children II

Medium

Rubrik

3 views

Topics:

ArraysDynamic Programming

You are given two positive integers n and limit.

Return the total number of ways to distribute n candies among 3 children such that no child gets more than limit candies.

Example 1:

Input: n = 5, limit = 2
Output: 3
Explanation: There are 3 ways to distribute 5 candies such that no child gets more than 2 candies: (1, 2, 2), (2, 1, 2) and (2, 2, 1).

Example 2:

Input: n = 3, limit = 3
Output: 10
Explanation: There are 10 ways to distribute 3 candies such that no child gets more than 3 candies: (0, 0, 3), (0, 1, 2), (0, 2, 1), (0, 3, 0), (1, 0, 2), (1, 1, 1), (1, 2, 0), (2, 0, 1), (2, 1, 0) and (3, 0, 0).

Constraints:

1 <= n <= 10⁶
1 <= limit <= 10⁶

Try coding it in LeetCode

Distribute Candies Among Children II

Medium

Rubrik

3 views

Topics:

ArraysDynamic Programming

You are given two positive integers n and limit.

Return the total number of ways to distribute n candies among 3 children such that no child gets more than limit candies.

Example 1:

Input: n = 5, limit = 2
Output: 3
Explanation: There are 3 ways to distribute 5 candies such that no child gets more than 2 candies: (1, 2, 2), (2, 1, 2) and (2, 2, 1).

Example 2:

Input: n = 3, limit = 3
Output: 10
Explanation: There are 10 ways to distribute 3 candies such that no child gets more than 3 candies: (0, 0, 3), (0, 1, 2), (0, 2, 1), (0, 3, 0), (1, 0, 2), (1, 1, 1), (1, 2, 0), (2, 0, 1), (2, 1, 0) and (3, 0, 0).

Constraints:

1 <= n <= 10⁶
1 <= limit <= 10⁶

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints for n, limit, and num_children? Specifically, what are the minimum and maximum possible values for each?
Is it possible for n to be greater than limit * num_children? If so, what should I return?
Is it possible for n, limit, or num_children to be zero?
Are we looking for the number of *distinct* ways to distribute the candies, or are different orderings of the same amounts given to each child considered different?
Should the return value be an integer type, and if so, what size? (e.g., 32-bit int, 64-bit int) Is there a possibility of integer overflow?

Brute Force Solution

Approach

The brute force approach for distributing candies is like trying every single possible way to give candies to the children. We start by giving the minimum amount to everyone and then explore all combinations of giving out the remaining candies one by one.

Here's how the algorithm would work step-by-step:

First, give each child the minimum number of candies they are entitled to.
Figure out how many candies are left over after giving everyone the minimum amount.
Now, try giving one extra candy to the first child, and see if it works. A solution works if we do not exceed the maximum number of candies any child can receive and we use up all the candies.
Then, try giving that extra candy to the second child instead, and see if that works.
Keep going, trying to give the extra candy to each child one by one.
If giving one extra candy doesn't work, try giving two extra candies to the first child, and then to the second, and so on.
Continue this process of trying to give different amounts of extra candy to each child in every possible combination.
For each combination, check if it satisfies the rules (everyone gets no more than the maximum candies allowed, and you use up all the candies).
Once we've checked every single possible combination, we will have found the correct distribution.

Code Implementation

def distribute_candies_brute_force(number_of_candies,
                                       number_of_children,
                                       limit_candies_per_child):

    candies_distribution = [0] * number_of_children

    # Give each child the minimum amount of candies possible
    candies_to_give = min(number_of_candies // number_of_children, limit_candies_per_child)

    for child_index in range(number_of_children):
        candies_distribution[child_index] = candies_to_give

    remaining_candies = number_of_candies - (candies_to_give * number_of_children)

    if remaining_candies == 0:
        return candies_distribution

    def backtrack(child_index, candies_left):
        nonlocal candies_distribution

        if candies_left == 0:
            return sum(candies_distribution) == number_of_candies

        if child_index == number_of_children:
            return False

        for candies_to_add in range(min(candies_left + 1,
                                        limit_candies_per_child -
                                        candies_distribution[child_index] + 1)):
            
            candies_distribution[child_index] += candies_to_add
            # Explore adding candies to this child
            if backtrack(child_index + 1, candies_left - candies_to_add):
                return True

            candies_distribution[child_index] -= candies_to_add

        return False

    # Iterate through each child to distribute the remaining candies
    if backtrack(0, remaining_candies):
        return candies_distribution
    #If no possible distribution is found
    candies_distribution = [0] * number_of_children
    candies_assigned = 0

    for i in range(number_of_children):
        candies_to_assign = min(limit_candies_per_child, number_of_candies - candies_assigned)
        candies_distribution[i] = candies_to_assign
        candies_assigned += candies_to_assign

    return candies_distribution

Big(O) Analysis

Time Complexity

O(c^n) – The brute force approach explores all possible combinations of distributing the remaining candies among n children. The number of combinations grows exponentially with the number of children (n) and the remaining candies (c) to distribute after giving each child the minimum. Trying every combination makes the runtime proportional to the number of these combinations, where each child can receive anywhere from 0 to c additional candies. Therefore, the time complexity is O(c^n) because for each child, there are 'c' choices and there are 'n' children. Thus, exponential time.

Space Complexity

O(1) – The brute force approach, as described, doesn't utilize any auxiliary data structures that scale with the number of children or the number of candies. It only involves updating the candy distribution in place and comparing sums. Therefore, the space complexity is constant, O(1), as it requires a fixed amount of extra memory regardless of the input size.

Optimal Solution

Approach

The problem asks us to distribute candies to children in a specific pattern until we run out of candies. The key insight is to calculate how many rounds of distribution we can complete fully before candies become insufficient for a full round, and then handle the remaining candies separately.

Here's how the algorithm would work step-by-step:

First, determine how many full cycles of candy distribution can be completed.
To do this, figure out how many candies are needed for one full cycle (from the first child to the last).
Then, divide the total number of candies by the number of candies needed for a full cycle to find the number of full cycles that can be completed.
Calculate how many candies are left after completing all the full cycles.
Distribute candies to each child based on the number of full cycles, remembering the pattern that determines how many candies a child gets in each cycle.
Finally, distribute the remaining candies, one child at a time, until there are no candies left, following the same candy distribution pattern.
The number of candies each child has at the end is the result.

Code Implementation

def distribute_candies(number_of_children, total_candies):
    candies_per_child = [0] * number_of_children
    children_in_cycle = number_of_children
    candies_for_full_cycle = (children_in_cycle * (children_in_cycle + 1)) // 2

    # Calculate how many full cycles we can complete
    number_of_full_cycles = 0
    if candies_for_full_cycle > 0:
        number_of_full_cycles = total_candies // candies_for_full_cycle

    remaining_candies = total_candies - number_of_full_cycles * candies_for_full_cycle

    # Distribute candies based on the full cycles
    for child_index in range(number_of_children):
        candies_per_child[child_index] = (child_index + 1) * number_of_full_cycles

    # Distribute the remaining candies
    child_index = 0
    candy_to_give = number_of_full_cycles * 1 + 1

    while remaining_candies > 0:
        # Distribute candies until we run out
        if remaining_candies >= candy_to_give:
            candies_per_child[child_index] += candy_to_give
            remaining_candies -= candy_to_give
            candy_to_give += 1
        else:
            candies_per_child[child_index] += remaining_candies
            remaining_candies = 0
        child_index += 1

    return candies_per_child

Big(O) Analysis

Time Complexity

O(n) – The algorithm involves calculating the number of full cycles, which takes constant time. Then, it iterates through all n children to distribute candies based on these full cycles. Finally, there's a single loop that distributes any remaining candies, iterating through the children at most once. Therefore, the dominant factor is the iteration through all n children, resulting in a time complexity of O(n).

Space Complexity

O(1) – The algorithm primarily involves arithmetic calculations and assignments to variables representing the number of candies given to each child. The space used is dominated by storing the total number of candies given to each child, which will be an array of size 'n' (number of children). Although the final result requires storing the candy count for each child, this is considered the output space, not auxiliary space. Thus, the auxiliary space used consists only of a few integer variables to track loops and intermediate calculations. This fixed amount of memory does not scale with the input size 'n', resulting in constant auxiliary space complexity.

Edge Cases

Case	How to Handle
n is zero (no candies)	If n is zero, return 1 if num_children is also zero or some combination of limit allows the children to have no candy, otherwise 0.
num_children is zero	If num_children is zero and n is also zero return 1, if n is non zero there is no way to distribute and return 0.
limit is zero	If limit is zero, return 1 only when n is also 0, and 0 otherwise.
n is negative	If n is negative, it's an invalid input and should return 0 since you cannot distribute negative candies.
limit is negative	If the limit is negative, it is an invalid input and should return 0 because a child can't have a negative candy limit.
n is much larger than num_children * limit	This means distribution is impossible, return 0.
Integer overflow in calculations	Use appropriate data types (e.g., long long in C++, long in Java) to prevent integer overflow during intermediate calculations, particularly when dealing with combinations.
n equals num_children * limit	There is only one way which is when each children gets the maximum candy allowed, return 1.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints for n, limit, and num_children? Specifically, what are the minimum and maximum possible values for each?
Is it possible for n to be greater than limit * num_children? If so, what should I return?
Is it possible for n, limit, or num_children to be zero?
Are we looking for the number of *distinct* ways to distribute the candies, or are different orderings of the same amounts given to each child considered different?
Should the return value be an integer type, and if so, what size? (e.g., 32-bit int, 64-bit int) Is there a possibility of integer overflow?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, give each child the minimum number of candies they are entitled to.
Figure out how many candies are left over after giving everyone the minimum amount.
Now, try giving one extra candy to the first child, and see if it works. A solution works if we do not exceed the maximum number of candies any child can receive and we use up all the candies.
Then, try giving that extra candy to the second child instead, and see if that works.
Keep going, trying to give the extra candy to each child one by one.
If giving one extra candy doesn't work, try giving two extra candies to the first child, and then to the second, and so on.
Continue this process of trying to give different amounts of extra candy to each child in every possible combination.
For each combination, check if it satisfies the rules (everyone gets no more than the maximum candies allowed, and you use up all the candies).
Once we've checked every single possible combination, we will have found the correct distribution.

Code Implementation

def distribute_candies_brute_force(number_of_candies,
                                       number_of_children,
                                       limit_candies_per_child):

    candies_distribution = [0] * number_of_children

    # Give each child the minimum amount of candies possible
    candies_to_give = min(number_of_candies // number_of_children, limit_candies_per_child)

    for child_index in range(number_of_children):
        candies_distribution[child_index] = candies_to_give

    remaining_candies = number_of_candies - (candies_to_give * number_of_children)

    if remaining_candies == 0:
        return candies_distribution

    def backtrack(child_index, candies_left):
        nonlocal candies_distribution

        if candies_left == 0:
            return sum(candies_distribution) == number_of_candies

        if child_index == number_of_children:
            return False

        for candies_to_add in range(min(candies_left + 1,
                                        limit_candies_per_child -
                                        candies_distribution[child_index] + 1)):
            
            candies_distribution[child_index] += candies_to_add
            # Explore adding candies to this child
            if backtrack(child_index + 1, candies_left - candies_to_add):
                return True

            candies_distribution[child_index] -= candies_to_add

        return False

    # Iterate through each child to distribute the remaining candies
    if backtrack(0, remaining_candies):
        return candies_distribution
    #If no possible distribution is found
    candies_distribution = [0] * number_of_children
    candies_assigned = 0

    for i in range(number_of_children):
        candies_to_assign = min(limit_candies_per_child, number_of_candies - candies_assigned)
        candies_distribution[i] = candies_to_assign
        candies_assigned += candies_to_assign

    return candies_distribution

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, determine how many full cycles of candy distribution can be completed.
To do this, figure out how many candies are needed for one full cycle (from the first child to the last).
Then, divide the total number of candies by the number of candies needed for a full cycle to find the number of full cycles that can be completed.
Calculate how many candies are left after completing all the full cycles.
Distribute candies to each child based on the number of full cycles, remembering the pattern that determines how many candies a child gets in each cycle.
Finally, distribute the remaining candies, one child at a time, until there are no candies left, following the same candy distribution pattern.
The number of candies each child has at the end is the result.

Code Implementation

def distribute_candies(number_of_children, total_candies):
    candies_per_child = [0] * number_of_children
    children_in_cycle = number_of_children
    candies_for_full_cycle = (children_in_cycle * (children_in_cycle + 1)) // 2

    # Calculate how many full cycles we can complete
    number_of_full_cycles = 0
    if candies_for_full_cycle > 0:
        number_of_full_cycles = total_candies // candies_for_full_cycle

    remaining_candies = total_candies - number_of_full_cycles * candies_for_full_cycle

    # Distribute candies based on the full cycles
    for child_index in range(number_of_children):
        candies_per_child[child_index] = (child_index + 1) * number_of_full_cycles

    # Distribute the remaining candies
    child_index = 0
    candy_to_give = number_of_full_cycles * 1 + 1

    while remaining_candies > 0:
        # Distribute candies until we run out
        if remaining_candies >= candy_to_give:
            candies_per_child[child_index] += candy_to_give
            remaining_candies -= candy_to_give
            candy_to_give += 1
        else:
            candies_per_child[child_index] += remaining_candies
            remaining_candies = 0
        child_index += 1

    return candies_per_child

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
n is zero (no candies)	If n is zero, return 1 if num_children is also zero or some combination of limit allows the children to have no candy, otherwise 0.
num_children is zero	If num_children is zero and n is also zero return 1, if n is non zero there is no way to distribute and return 0.
limit is zero	If limit is zero, return 1 only when n is also 0, and 0 otherwise.
n is negative	If n is negative, it's an invalid input and should return 0 since you cannot distribute negative candies.
limit is negative	If the limit is negative, it is an invalid input and should return 0 because a child can't have a negative candy limit.
n is much larger than num_children * limit	This means distribution is impossible, return 0.
Integer overflow in calculations	Use appropriate data types (e.g., long long in C++, long in Java) to prevent integer overflow during intermediate calculations, particularly when dealing with combinations.
n equals num_children * limit	There is only one way which is when each children gets the maximum candy allowed, return 1.