We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Distribute Candies

Number: 575

Difficulty: Easy

Paid? No

Companies: LiveRamp

Problem Description

Alice has n candies, where candyType[i] represents the type of the i-th candy. However, she can only eat n/2 candies due to a doctor's advice. The goal is to maximize the number of different candy types that Alice can eat given this constraint.

Key Insights

  • The maximum number of different candies Alice can eat is limited by both the number of unique candy types and n/2.
  • Using a set to store the unique candy types from the array helps in counting them efficiently.
  • The final answer is simply the minimum between the number of unique candy types and n/2.

Space and Time Complexity

Time Complexity: O(n), where n is the number of candies. We iterate the array once to populate the set of unique types.
Space Complexity: O(n) in the worst case, if every candy is of a unique type.

Solution

We solve this problem by leveraging a set to capture all unique candy types. After converting the candy list into a set, we count the unique elements. Since Alice is restricted to eat n/2 candies, the result is the minimum of the unique count and n/2. This approach is both simple and efficient, taking only linear time relative to the size of the input.

Code Solutions

# Python solution

def distributeCandies(candyType):
    # Convert the list into a set to capture unique candy types
    unique_candies = set(candyType)
    # Calculate the maximum number of candies Alice can eat (n/2)
    max_candies = len(candyType) // 2
    # The answer is the minimum of unique candy types and max_candies
    return min(len(unique_candies), max_candies)

# Example usage:
print(distributeCandies([1,1,2,2,3,3]))  # Expected Output: 3
print(distributeCandies([1,1,2,3]))      # Expected Output: 2
print(distributeCandies([6,6,6,6]))      # Expected Output: 1
← Back to All Questions