Distribute Candies LeetCode

In the world of sharing and fairness, the distribute candies challenge of LeetCode is really interesting. It’s about figuring out how to give a limited number of candies to a group of people so that everyone gets a fair amount, following certain rules. This problem is like real-life situations where we have to share resources fairly, like giving money to different departments of an organization or distributing supplies to people affected by some disaster.

Problem statement

We are given $n$ even number of candies of different types, and the type of candy $i$ is $candyType[i]$ . Now, we have decided to share half of our candies with a sibling, and we want to give them the maximum types of candies so that they can taste the maximum.

Our task is to determine the maximum number of different candies that we can share. The result would be a number of different types of candies. Let’s try to map our problem into a visual for better understanding.

Educative-99 helps you solve complex coding problems like distribute candies by teaching you to recognize patterns and apply the right algorithms.

Algorithm

There are $n$ number of candies. Let’s assume $c$ as the type of candies. If the types of candies $c$ are less than half of the candies, we can choose all types of candies $c$ as output. If half of the candies are less than the total types of candies $c$ , we've to choose $\frac{n}{2}$ types of candies.

Let’s write down the algorithm steps:

Find the total number of candies to share (half of the total candies).
Find the total number of types of candies (unique candies).
If the types of candies are less than the total number of candies to be shared, return the total types of candies.
Otherwise, return half of the total number of candies.

def distributeCandies(candyType: list[int]) -> int:
    max_candies = len(candyType)//2     # finding the total number of candies to be shared
    unique_candies = len(set(candyType))    # finding the total number of types of candies
    
    # checking if the unique_candies are less than the maximum candies to be shared
    if unique_candies < max_candies:
        return unique_candies   # return the unique_candies
    
    return max_candies  # otherwise return the max_candies to be shared
# ---------------------------------------------------------------------
candySet1 = [1, 1, 2, 2, 3, 3] # candy set 1
print("For the candy set:", candySet1, end="")
print(", we can share", distributeCandies(candySet1), "type(s) of candies!")
candySet2 = [1, 1, 2, 3] # candy set 2
print("For the candy set:", candySet2, end="")
print(", we can share", distributeCandies(candySet2), "type(s) of candies!")
candySet3 = [6, 6, 6, 6] # candy set 3
print("For the candy set:", candySet3, end="")
print(", we can share", distributeCandies(candySet3), "type(s) of candies!")
candySet4 = ['🍬', '🍭', '🍫', '🍡', '🍪', '🌰', '🍬', '🍬', '🍭', '🍫'] # candy set 4
print("For the candy set:", candySet4, end="")
print(", we can share", distributeCandies(candySet4), "type(s) of candies!")

Solution of the distribute candies problem in Python

Time complexity

In the above implementation, we use:

Finding the length takes the constant time: $O(1)$ .
Finding unique elements takes the linear time: $O(n)$ .
Condition check takes the constant time: $O(1)$ .

By the above distribution, the time complexity is linear: $O(n)$ .

Space complexity

In the above implementation, we use:

Two variables to store two integer values.
The set of unique candies to store at most $n$ elements.

By the above distribution, the space complexity is linear: $O(n)$ .

Distribute Candies LeetCode

Problem statement

Algorithm

Knowledge test

Coding example

Time complexity

Space complexity