Jobs

Interviews

Discussions

Distribute Candies Among Children II

Medium

Amazon

1 view

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.

For example:

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).

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).

Distribute Candies Among Children II

Medium

Amazon

1 view

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.

For example:

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).

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 on the number of children (n) and the total number of candies (limit)?
Can the number of candies to distribute (limit) be zero? Can the number of children (n) be zero or one?
If not all candies can be distributed according to the rules, what should be the state of the distribution array at the end?
What data type should I use for the distribution array and for the inputs n and limit? (e.g., int, long)
Is there any specific requirement for how the candies should be distributed beyond the given rules (e.g., minimizing the difference between adjacent children)? If multiple valid distributions exist, is any one acceptable?

Brute Force Solution

Approach

The brute force method for distributing candies tries every single possible distribution of candies to the children. We'll explore each possibility until we find one that satisfies the rules, by manually assigning different numbers of candies to the children in a systematic fashion.

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

Start by giving the first child zero candies, and then try giving them one candy, then two candies, and so on until you've explored all possibilities for that child.
For each number of candies you give the first child, determine how many candies are left.
Now, give the second child zero candies, then one candy, and so on, up to the number of candies remaining after you gave some to the first child.
Continue this pattern for each child, always making sure you don't give away more candies than you have available at that point.
Once you've given candies to all the children, check if you've used all the candies you were supposed to distribute. If you haven't used all candies or any child received more candies than the limit, this distribution is invalid.
Keep track of every valid distribution you find.
After you've explored every possible distribution, pick the best one based on the given question's criteria to minimize candy distribution.

Code Implementation

def distribute_candies_brute_force(number_of_children, total_candies, candy_limit):
    best_distribution = None

    def find_distributions(current_child_index, remaining_candies, current_distribution):
        nonlocal best_distribution

        # Base case: all children have been considered
        if current_child_index == number_of_children:
            if remaining_candies == 0:

                #Check if current distribution is valid and update the best found
                if best_distribution is None:
                    best_distribution = current_distribution[:]
                
            return

        # Iterate through all possible candy amounts for the current child
        for current_candies in range(min(remaining_candies + 1, candy_limit + 1)):

            #The recursive case explores giving different number of candies
            current_distribution[current_child_index] = current_candies
            find_distributions(current_child_index + 1, remaining_candies - current_candies, current_distribution)

    current_distribution = [0] * number_of_children
    find_distributions(0, total_candies, current_distribution)

    return best_distribution

Big(O) Analysis

Time Complexity

O(c^n) – The brute force approach explores every possible distribution of candies to the children. We have 'n' children, and each child can receive anywhere from 0 to 'c' candies, where 'c' is the candy limit. This creates a nested loop structure where, in the worst case, we iterate 'c' times for each of the 'n' children. Thus, the time complexity grows exponentially with the number of children, resulting in O(c^n).

Space Complexity

O(1) – The brute force method described does not explicitly mention the creation of any auxiliary data structures such as lists, hash maps, or sets. While the algorithm explores different distributions, it checks them one by one without storing all of them simultaneously. Therefore, it only uses a few constant space variables to keep track of the current distribution being explored and the best distribution found so far. The space used does not depend on the input size (number of children or candies). Consequently, the space complexity is O(1).

Optimal Solution

Approach

This problem is best solved by first figuring out how many complete rounds of candy distribution we can perform. Then, we handle the remaining candy to ensure everyone gets their fair share, up to the maximum allowed.

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

First, calculate how many full rounds of candy we can give out, considering the increasing amounts for each child.
Determine how much candy would be left after these full rounds.
Distribute candy to each child based on the full rounds, taking into account the increasing amounts in each round.
Starting from the beginning, give each child their share of the remaining candy, but stop when a child reaches the maximum candy limit or when we run out of candy.
Carefully check if any child should receive less candy than calculated because we ran out of candies, ensuring no one receives more than the maximum or all candies were distributed.

Code Implementation

def distributeCandies(number_of_children, total_candies, maximum_candies):

    candies_distributed = [0] * number_of_children
    children_in_round = number_of_children
    total_in_one_round = (children_in_round * (children_in_round + 1)) // 2

    rounds_completed = 0
    if total_candies >= total_in_one_round:
        
        left = 0
        right = int((2 * total_candies)**0.5)
        while left <= right:
            mid = (left + right) // 2
            total_needed = mid * total_in_one_round + mid * (mid - 1) // 2 * children_in_round
            if total_needed <= total_candies:
                rounds_completed = mid
                left = mid + 1
            else:
                right = mid - 1

    # Calculate remaining candies after completed rounds.
    remaining_candies = total_candies
    if rounds_completed > 0:
        remaining_candies -= (rounds_completed * total_in_one_round + rounds_completed * (rounds_completed - 1) // 2 * children_in_round)

    # Distribute candies based on the full rounds.
    for child_index in range(number_of_children):
        candies_distributed[child_index] = (child_index + 1) * rounds_completed + (rounds_completed * (rounds_completed - 1) // 2) 

    # Distribute the remaining candies to the children.
    for child_index in range(number_of_children):
        candies_to_give = min(child_index + 1 + rounds_completed * number_of_children, maximum_candies)
        
        if remaining_candies > 0:
            give = min(candies_to_give - candies_distributed[child_index], remaining_candies)
            
            if give > 0:
                candies_distributed[child_index] += give
                remaining_candies -= give

        # Ensure no child receives more than the maximum.
        candies_distributed[child_index] = min(candies_distributed[child_index], maximum_candies)

    return candies_distributed

Big(O) Analysis

Time Complexity

O(n) – The algorithm first calculates the number of complete rounds, which involves constant time operations. After that, it iterates through the children once to distribute candies based on the full rounds and any remaining candy, ensuring no one exceeds the limit. This single pass through the array of size n dominates the time complexity. Therefore, the overall time complexity is O(n).

Space Complexity

O(1) – The provided steps describe an iterative process that primarily involves arithmetic calculations and comparisons. There's no mention of auxiliary data structures like arrays, lists, or hash maps that would grow with the number of children (N). The algorithm seems to use a few constant space variables to keep track of rounds and remaining candy. Thus, the auxiliary space complexity is constant, independent of the input size N.

Edge Cases

Case	How to Handle
n = 0 or k = 0	Return an array of n zeros since no candies can be distributed.
k is very large (greater than or equal to n*(n+1)/2) such that first round distributes all candies.	Return an array where the first element is k, and rest are 0s.
candies (k) is very large and close to long.MaxValue which can cause integer overflow if we calculate candies distributed in naive way.	Use long data type for all calculations related to candies to prevent potential integer overflows.
n = 1	Return an array with one element k, as all candies can be given to a single child.
k is smaller than n (not enough candies for initial distribution)	Distribute candies sequentially until candies run out, filling the remaining elements with zero.
k allows for a complete first round, and some additional but not enough for a full second round, but enough for a few subsequent rounds	Continue rounds while possible until k is less than or equal to current round number plus previous candy distributed in initial round.
k is just enough to fill some children at the end after completing several rounds where (k - sum of all distributed candies < (current round count + initial_candy) )	The final loop distributes remaining candies sequentially until the remainder is zero.
n is very large, potentially causing performance issues if the solution involves repeated iterations of the array.	Optimize candy distribution by calculating complete rounds without explicit looping, and then handling remainder candies with the remaining children.

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 on the number of children (n) and the total number of candies (limit)?
Can the number of candies to distribute (limit) be zero? Can the number of children (n) be zero or one?
If not all candies can be distributed according to the rules, what should be the state of the distribution array at the end?
What data type should I use for the distribution array and for the inputs n and limit? (e.g., int, long)
Is there any specific requirement for how the candies should be distributed beyond the given rules (e.g., minimizing the difference between adjacent children)? If multiple valid distributions exist, is any one acceptable?

Brute Force Solution

Approach

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

Start by giving the first child zero candies, and then try giving them one candy, then two candies, and so on until you've explored all possibilities for that child.
For each number of candies you give the first child, determine how many candies are left.
Now, give the second child zero candies, then one candy, and so on, up to the number of candies remaining after you gave some to the first child.
Continue this pattern for each child, always making sure you don't give away more candies than you have available at that point.
Once you've given candies to all the children, check if you've used all the candies you were supposed to distribute. If you haven't used all candies or any child received more candies than the limit, this distribution is invalid.
Keep track of every valid distribution you find.
After you've explored every possible distribution, pick the best one based on the given question's criteria to minimize candy distribution.

Code Implementation

def distribute_candies_brute_force(number_of_children, total_candies, candy_limit):
    best_distribution = None

    def find_distributions(current_child_index, remaining_candies, current_distribution):
        nonlocal best_distribution

        # Base case: all children have been considered
        if current_child_index == number_of_children:
            if remaining_candies == 0:

                #Check if current distribution is valid and update the best found
                if best_distribution is None:
                    best_distribution = current_distribution[:]
                
            return

        # Iterate through all possible candy amounts for the current child
        for current_candies in range(min(remaining_candies + 1, candy_limit + 1)):

            #The recursive case explores giving different number of candies
            current_distribution[current_child_index] = current_candies
            find_distributions(current_child_index + 1, remaining_candies - current_candies, current_distribution)

    current_distribution = [0] * number_of_children
    find_distributions(0, total_candies, current_distribution)

    return best_distribution

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, calculate how many full rounds of candy we can give out, considering the increasing amounts for each child.
Determine how much candy would be left after these full rounds.
Distribute candy to each child based on the full rounds, taking into account the increasing amounts in each round.
Starting from the beginning, give each child their share of the remaining candy, but stop when a child reaches the maximum candy limit or when we run out of candy.
Carefully check if any child should receive less candy than calculated because we ran out of candies, ensuring no one receives more than the maximum or all candies were distributed.

Code Implementation

def distributeCandies(number_of_children, total_candies, maximum_candies):

    candies_distributed = [0] * number_of_children
    children_in_round = number_of_children
    total_in_one_round = (children_in_round * (children_in_round + 1)) // 2

    rounds_completed = 0
    if total_candies >= total_in_one_round:
        
        left = 0
        right = int((2 * total_candies)**0.5)
        while left <= right:
            mid = (left + right) // 2
            total_needed = mid * total_in_one_round + mid * (mid - 1) // 2 * children_in_round
            if total_needed <= total_candies:
                rounds_completed = mid
                left = mid + 1
            else:
                right = mid - 1

    # Calculate remaining candies after completed rounds.
    remaining_candies = total_candies
    if rounds_completed > 0:
        remaining_candies -= (rounds_completed * total_in_one_round + rounds_completed * (rounds_completed - 1) // 2 * children_in_round)

    # Distribute candies based on the full rounds.
    for child_index in range(number_of_children):
        candies_distributed[child_index] = (child_index + 1) * rounds_completed + (rounds_completed * (rounds_completed - 1) // 2) 

    # Distribute the remaining candies to the children.
    for child_index in range(number_of_children):
        candies_to_give = min(child_index + 1 + rounds_completed * number_of_children, maximum_candies)
        
        if remaining_candies > 0:
            give = min(candies_to_give - candies_distributed[child_index], remaining_candies)
            
            if give > 0:
                candies_distributed[child_index] += give
                remaining_candies -= give

        # Ensure no child receives more than the maximum.
        candies_distributed[child_index] = min(candies_distributed[child_index], maximum_candies)

    return candies_distributed

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
n = 0 or k = 0	Return an array of n zeros since no candies can be distributed.
k is very large (greater than or equal to n*(n+1)/2) such that first round distributes all candies.	Return an array where the first element is k, and rest are 0s.
candies (k) is very large and close to long.MaxValue which can cause integer overflow if we calculate candies distributed in naive way.	Use long data type for all calculations related to candies to prevent potential integer overflows.
n = 1	Return an array with one element k, as all candies can be given to a single child.
k is smaller than n (not enough candies for initial distribution)	Distribute candies sequentially until candies run out, filling the remaining elements with zero.
k allows for a complete first round, and some additional but not enough for a full second round, but enough for a few subsequent rounds	Continue rounds while possible until k is less than or equal to current round number plus previous candy distributed in initial round.
k is just enough to fill some children at the end after completing several rounds where (k - sum of all distributed candies < (current round count + initial_candy) )	The final loop distributes remaining candies sequentially until the remainder is zero.
n is very large, potentially causing performance issues if the solution involves repeated iterations of the array.	Optimize candy distribution by calculating complete rounds without explicit looping, and then handling remainder candies with the remaining children.