575 Distribute Candies

1. Description

Alice has n candies, where ith candy is of type candyType[i]. Alice noticed that she started to gain weight, so she visited a doctor.

 

The doctor advised Alice to only eat n / 2 of the candies she has (n is always even). Alice likes her candies very much, and she wants to each to eat maximum number of different types of candies whilte still following the doctor's advice.

 

Given the integer array candyType of length n, return the maximum number of different types of candies she can eat if she only eats n/2 of them.

 

constraints :

• n == candyType.length
• 2 <= n <= \(10^{4}\)
• n is even.
• \(-10^{5}\) <= candyType[i] <= \(10^{5}\)

 

2. Algorithms

What we want to see is the maximum number of different types of candies. There two cases when we make frequency table of input list. Let's consider the length of frequency table as n_freq and the length of input list as n.

• n_freq >= n/2 : We can eat n/2 of the candies.
• n_freq < n/2 : We can only eat n_freq of the candies.

 

1. Start
2. Store the length of input list candyType into variable named n.
3. Make frequency table using Counter method.
4. Store the lenght of frequency table into variable named n_freq.
5. If n_freq >= n, return n/2.
6. Else, return n_freq.
7. End

 

We can use set to make algorithm more faster.

1. Start
2. Make set from input list and store result into set.
3. Store the length of input list candyType into variable named n.
4. Store the length of set into variable named n_freq.
5. Store the length of doctor's advise into variable named n_doctor. (n/2)
6. Return the smallest value between n_freq and n_doctor.
7. End

3. Codes

# Algorithm1

class Solution:
    def distributeCandies(self, candyType: List[int]) -> int:
        n = len(candyType)
        freq = Counter(candyType) 
        n_freq = len(freq) 
        
        if n_freq >= n/2 : 
            return int(n/2)
        else : 
            return n_freq
            
# Algorithm2

class Solution:
    def distributeCandies(self, candyType: List[int]) -> int:
        n = len(candyType) 
        candySet = set(candyType) 
        n_freq = len(candySet) 
        n_doctor = int(n/2)
        return min(n_freq, n_doctor)

4. Conclusion