Distribute Candies


  • 0

    Click here to see the full article post


  • 1
    D

    Using sorting Time complexity : O(n)? ?


  • 0

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


  • 0

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


  • 0

    @dxy_1993 @ StefanPochmann I have updated it. Thanks.


  • 0

    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")


  • 0
    I

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


  • 0
    C

    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))


  • -1
    A

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


  • -1
    A

    """"
    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())
    """"


  • -1
    S

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


  • -1
    H

    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)


  • -1
    M

    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();
    }
    }


  • -1
    L

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


Log in to reply
 

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