Jobs

Interviews

Discussions

Distribute Candies Among Children I

Easy

Rubrik

5 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 <= 50
1 <= limit <= 50

Try coding it in LeetCode

Distribute Candies Among Children I

Easy

Rubrik

5 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 <= 50
1 <= limit <= 50

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 possible ranges for the number of candies and the number of children? Are they always positive integers?
What should I return if the number of children is zero? Is that a valid input?
If the candies cannot be evenly distributed (some candies would be left over), should I return 0, throw an error, or is there another specific expected return value?
Is it guaranteed that the number of candies will always be greater than or equal to the number of children, or should I handle the case where there are more children than candies?
Could the number of candies or children be very large (e.g., approaching the maximum integer value), and do I need to be concerned about potential integer overflow?

Brute Force Solution

Approach

The brute force approach to distributing candies tries out every possible way to give candies to the children. We explore all combinations to find a solution that meets the criteria. This method is like trying every single possibility until we find the right one.

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

Start by giving one candy to the first child, then give one candy to the second child, and so on, until every child has at least one candy.
After this initial distribution, explore every possible combination of giving out the remaining candies.
For each combination, check if it follows the rule that a child with a higher rating than their neighbor must receive more candies.
If a distribution doesn't follow this rule, discard it and try a different one.
Keep track of all the possible candy distributions that satisfy the rule.
Calculate the total number of candies used for each valid distribution.
Finally, choose the candy distribution that uses the minimum total number of candies from all the valid distributions.

Code Implementation

def distribute_candies_brute_force(ratings):
    number_of_children = len(ratings)
    if number_of_children <= 0:
        return 0

    minimum_candies = float('inf')

    def is_valid_distribution(candies):
        # Check if the current candy distribution satisfies the given condition.
        for index in range(number_of_children):
            if index > 0 and ratings[index] > ratings[index - 1] and candies[index] <= candies[index - 1]:
                return False
            if index < number_of_children - 1 and ratings[index] > ratings[index + 1] and candies[index] <= candies[index + 1]:
                return False
        return True

    def find_minimum_candies(index, current_candies, total_candies_used):
        nonlocal minimum_candies

        if index == number_of_children:
            # Base case: all children have been assigned candies.
            if is_valid_distribution(current_candies):
                minimum_candies = min(minimum_candies, total_candies_used)
            return

        # Try all possible numbers of candies for the current child.
        for number_of_candies in range(1, sum(ratings) + 1):
            current_candies[index] = number_of_candies

            find_minimum_candies(index + 1, current_candies[:], total_candies_used + number_of_candies)

    # Start with each child having at least one candy.
    initial_candies = [1] * number_of_children
    
    find_minimum_candies(0, initial_candies, number_of_children)
    
    return minimum_candies

Big(O) Analysis

Time Complexity

O(C(n+k-1, k-1)) – The brute force approach explores all possible ways to distribute the candies. After giving each child one candy initially, we are left with 'k' remaining candies to distribute among 'n' children. The number of ways to distribute 'k' identical items among 'n' distinct containers is given by the combination with repetition formula C(n+k-1, k-1), where n is the number of children and k is the number of remaining candies to distribute. Thus, the time complexity is determined by the number of possible candy distributions. In each distribution, we must also validate if the higher rating neighbor rule is satisfied which takes O(n) time in the worst case. Therefore the total time complexity can be thought of as O(n * C(n+k-1, k-1)), but the combination term dominates so we can approximate to O(C(n+k-1, k-1)).

Space Complexity

O(N^N) – The brute force approach explores every possible combination of candy distribution. In the worst-case scenario, each child can potentially receive any number of candies up to the total number of candies. Storing all these possible distributions, even temporarily, requires significant space. If N is the number of children and the total number of candies is also proportional to N, the number of possible distributions grows exponentially with N. Therefore, auxiliary space for tracking these combinations would approximate to something like N^N, dominating other space usage.

Optimal Solution

Approach

The goal is to give candies to children standing in a line, where each child gets more candies than their neighbors if they have a higher rating. The most efficient way to do this is to consider the line twice - once from left to right and once from right to left - to ensure both neighbors are accounted for.

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

First, give every child one candy.
Then, go through the line from left to right. If a child has a higher rating than the child to their left, give them one more candy than the child to their left.
Next, go through the line from right to left. If a child has a higher rating than the child to their right, make sure they have at least one more candy than the child to their right. Take the maximum of their current number of candies and one more than the child to their right.
Finally, add up the number of candies each child has. This total is the minimum number of candies needed to satisfy the condition.

Code Implementation

def distribute_candies(ratings):
    number_of_children = len(ratings)
    candies = [1] * number_of_children

    # Ensure left neighbors with higher ratings get more candies
    for i in range(1, number_of_children):
        if ratings[i] > ratings[i - 1]:
            candies[i] = candies[i - 1] + 1

    # Ensure right neighbors with higher ratings get more candies
    for i in range(number_of_children - 2, -1, -1):
        if ratings[i] > ratings[i + 1]:

            #We need to consider what the child already has
            candies[i] = max(candies[i], candies[i + 1] + 1)

    total_candies = 0

    #Total the result for the final number of candies
    for candy_count in candies:
        total_candies += candy_count

    return total_candies

Big(O) Analysis

Time Complexity

O(n) – The algorithm involves iterating through the array of ratings twice, once from left to right and once from right to left. Each of these iterations visits each of the n children in the line exactly once. After these two passes, summing the number of candies each child has takes another O(n) operation. Therefore, the time complexity is O(n) + O(n) + O(n), which simplifies to O(n).

Space Complexity

O(N) – The algorithm uses an array of size N, where N is the number of children, to store the number of candies each child receives. This 'candies' array is initialized with each child receiving one candy, and then updated based on the ratings of neighboring children. Therefore, the auxiliary space used scales linearly with the number of children. The space complexity is O(N).

Edge Cases

Case	How to Handle
candies is zero	Return 0 if there are zero candies since no child can receive any.
children is zero	Return 0 if there are no children because division by zero is undefined, and no candies can be distributed.
candies is negative	Return 0 as distributing negative candies is not logically possible; consider throwing an exception based on problem requirements.
children is negative	Return 0, or throw an exception because having a negative number of children is not possible.
candies is less than children	Return 0 since not all children can receive at least one candy without leftover candies.
candies is equal to children	Return 1 as each child receives one candy each with no remainder.
Integer overflow if candies or children is very large	Use a data type that can hold very large numbers, or explicitly check for potential overflow during calculations.
Very large inputs that could cause performance issues	The division operation is O(1) and will perform efficiently even with large inputs.

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 possible ranges for the number of candies and the number of children? Are they always positive integers?
What should I return if the number of children is zero? Is that a valid input?
If the candies cannot be evenly distributed (some candies would be left over), should I return 0, throw an error, or is there another specific expected return value?
Is it guaranteed that the number of candies will always be greater than or equal to the number of children, or should I handle the case where there are more children than candies?
Could the number of candies or children be very large (e.g., approaching the maximum integer value), and do I need to be concerned about potential integer overflow?

Brute Force Solution

Approach

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

Start by giving one candy to the first child, then give one candy to the second child, and so on, until every child has at least one candy.
After this initial distribution, explore every possible combination of giving out the remaining candies.
For each combination, check if it follows the rule that a child with a higher rating than their neighbor must receive more candies.
If a distribution doesn't follow this rule, discard it and try a different one.
Keep track of all the possible candy distributions that satisfy the rule.
Calculate the total number of candies used for each valid distribution.
Finally, choose the candy distribution that uses the minimum total number of candies from all the valid distributions.

Code Implementation

def distribute_candies_brute_force(ratings):
    number_of_children = len(ratings)
    if number_of_children <= 0:
        return 0

    minimum_candies = float('inf')

    def is_valid_distribution(candies):
        # Check if the current candy distribution satisfies the given condition.
        for index in range(number_of_children):
            if index > 0 and ratings[index] > ratings[index - 1] and candies[index] <= candies[index - 1]:
                return False
            if index < number_of_children - 1 and ratings[index] > ratings[index + 1] and candies[index] <= candies[index + 1]:
                return False
        return True

    def find_minimum_candies(index, current_candies, total_candies_used):
        nonlocal minimum_candies

        if index == number_of_children:
            # Base case: all children have been assigned candies.
            if is_valid_distribution(current_candies):
                minimum_candies = min(minimum_candies, total_candies_used)
            return

        # Try all possible numbers of candies for the current child.
        for number_of_candies in range(1, sum(ratings) + 1):
            current_candies[index] = number_of_candies

            find_minimum_candies(index + 1, current_candies[:], total_candies_used + number_of_candies)

    # Start with each child having at least one candy.
    initial_candies = [1] * number_of_children
    
    find_minimum_candies(0, initial_candies, number_of_children)
    
    return minimum_candies

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, give every child one candy.
Then, go through the line from left to right. If a child has a higher rating than the child to their left, give them one more candy than the child to their left.
Next, go through the line from right to left. If a child has a higher rating than the child to their right, make sure they have at least one more candy than the child to their right. Take the maximum of their current number of candies and one more than the child to their right.
Finally, add up the number of candies each child has. This total is the minimum number of candies needed to satisfy the condition.

Code Implementation

def distribute_candies(ratings):
    number_of_children = len(ratings)
    candies = [1] * number_of_children

    # Ensure left neighbors with higher ratings get more candies
    for i in range(1, number_of_children):
        if ratings[i] > ratings[i - 1]:
            candies[i] = candies[i - 1] + 1

    # Ensure right neighbors with higher ratings get more candies
    for i in range(number_of_children - 2, -1, -1):
        if ratings[i] > ratings[i + 1]:

            #We need to consider what the child already has
            candies[i] = max(candies[i], candies[i + 1] + 1)

    total_candies = 0

    #Total the result for the final number of candies
    for candy_count in candies:
        total_candies += candy_count

    return total_candies

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
candies is zero	Return 0 if there are zero candies since no child can receive any.
children is zero	Return 0 if there are no children because division by zero is undefined, and no candies can be distributed.
candies is negative	Return 0 as distributing negative candies is not logically possible; consider throwing an exception based on problem requirements.
children is negative	Return 0, or throw an exception because having a negative number of children is not possible.
candies is less than children	Return 0 since not all children can receive at least one candy without leftover candies.
candies is equal to children	Return 1 as each child receives one candy each with no remainder.
Integer overflow if candies or children is very large	Use a data type that can hold very large numbers, or explicitly check for potential overflow during calculations.
Very large inputs that could cause performance issues	The division operation is O(1) and will perform efficiently even with large inputs.