# Distribute Candies

• Using sorting Time complexity : O(n)? ?

• Very interesting question, and I used the 'Approach #4 Using set [Accepted]'.

• @dxy_1993 Probably a copy&paste error, the "Size of recursion tree can go upto n" doesn't make much sense here :-)

• @dxy_1993 @ StefanPochmann I have updated it. Thanks.

• I doubt the space complexity O(1) for the sorting solution. I'd expect at least logarithmic space usage. And a quick look at the source suggests that it even takes linear space (though I didn't read it all).

(edit: fixed typo "linear time" to "linear space")

• Approach 4 may be optimized by set a termination condition when putting the new element into the Hashset.

• For me the best solution is to simulate giving each unique candy to the sister and then limit this number to half of the candies.
It runs in 2 lines of Python:
sister = set(candies)
return int(min(len(sister), len(candies)/2))

• """
class Solution(object):
def distributeCandies(self, candy):
return min(len(set(candy)), len(candy)/2)
"""

• """"
def distributedCandies(candy):
freq = {}
for i in candy:
freq[i] = freq.get(i,0)+1
if len(freq.keys()) > len(candy)/2:
return len(candy)/2
else:
return len(freq.keys())
""""

• class Solution:
def distributeCandies(self, candies):
freq = set()
for i in candies:
if len(freq) > len(candies) / 2:
return int(len(candies) / 2)
else:
return int(len(freq))

• class Solution:
def distributeCandies(self, candies):
"""
:type candies: List[int]
:rtype: int
"""
s = set(candies)
l = int(len(candies)/2)
if len(s) >= l:
return l
return len(s)

• class Solution {
public int distributeCandies(int[] candies) {
Map<Integer,Integer> maps = new HashMap<Integer,Integer>();
for(int i=0;i<candies.length;i++){
maps.put(candies[i],1);
}
return maps.size()>candies.length/2 ? candies.length/2 : maps.size();
}
}

• class Solution(object):
def distributeCandies(self, candies):
return min(len(set(candies)),int(len(candies)/2))

• Approach 1：If the array length is greater than 10, the speed will be very slow，but you can learn the idea of all permutations in it

• Also this could be improved:

1. use BitSet instead of Set (more memory consumption, but much faster)
2. finish fast when set.size() == candies.length / 2. No need to count after this condition is achieved.

• Following is my python soluton:
candyType = set(candies)
return min(len(candyType), len(candies)//2)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.