C# [O(n)]: Pragmatic Approach (Easy to Understand; With Comments)

  • 1

    Hey all

    I used a kinda common sense approach to solving this problem. I imagined that the brother and sister were real and dealt with it the way I would in real life; (revealing me to be a terribly unjust uncle).

    My solution ended up being surprisingly efficient so I decided to share it.

    public int DistributeCandies(int[] candies) {
            var uniqueCandies = new Dictionary<int, int>();
            // Count the number of TYPES of candies by adding each type to a list (using a hash).
            foreach (var candy in candies)
                uniqueCandies[candy] = 1;
            // Assume that the sister will get one of each TYPE of candy and that her brother gets the rest.
            // (This assumes she gets the maximum possible number of TYPES of candies.)
            int sistersCandies = uniqueCandies.Keys.Count;
            int brothersCandies = candies.Length - sistersCandies;
            // The only time she wouldn't get this maximum number of candies is if she has MORE candies than her brother.
            // In this case, she needs to share so that they have at least got the same number of candies.
            // In other words, she splits the difference with her brother.
            int diff = sistersCandies - brothersCandies;
            if (diff <= 0)
                return sistersCandies;
            // Split the difference:
            return sistersCandies - (diff / 2);

Log in to reply

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