Example 1:
Input: candies = [1,1,2,2,3,3] Output: 3 Explanation: There are three different kinds of candies (1, 2 and 3), and two candies for each kind. Optimal distribution: The sister has candies [1,2,3] and the brother has candies [1,2,3], too. The sister has three different kinds of candies.
Example 2:
Input: candies = [1,1,2,3] Output: 2 Explanation: For example, the sister has candies [2,3] and the brother has candies [1,1]. The sister has two different kinds of candies, the brother has only one kind of candies.
Note:
Algorithm
The brute force approach is really simple. We can generate all the permutations of the given array representing the candies and determine the number of unique elements in the first half of the generated array.
In order to determine the number of unique elements in the first half of the array, we put all the required elements in a set and count the number of elements in the set. We count such unique elements in the first half of the generated arrays for all the permutations possible and return the size of the largest set.
Complexity Analysis
Time complexity : . A total of permutations are possible for array of size .
Space complexity : . The depth of the recursion tree can go upto .
Algorithm
Before looking into the idea behind this approach, firstly we need to observe one point. The maximum no. of unique candies which the girl can obtain could be atmost , where refers to the number of candies. Further, in case the number of unique candies are below , to maximize the number of unique candies that the girl will obtain, we'll assign all the unique candies to the girl. Thus, in such a case, the number of unique candies the girl gets is equal to the total number of unique candies in the given array.
Now, let's look at the idea behind this approach. We need to find the total number of unique candies in the given array. One way to find the number of unique candies is to traverse over the given array. Whenever we encounter an element, say , we can mark all the elements which are the same as as invalid and increment the count of unique elements by 1.
Thus, we need to do such markings for all the elements of array. At the end, gives the required number of unique candies that can be given to the girl. Further, the value to be returned is given by: . Instead of finding the , we can stop the traversal over the given array as soon as the exceeds .
Complexity Analysis
Time complexity : . We traverse over all the elements of for every new element found. In the worst case, we do so for every element of array. refers to the size of array.
Space complexity : . Constant space is used.
Algorithm
We can sort the given array and find out the elements which are unique by comparing the adjacent elements of the sorted array. For every new element found(which isn't the same as the previous element), we need to update the . At the end, we can return the required result as , as discussed in the previous approach.
Complexity Analysis
Time complexity : . Sorting takes time.
Space complexity : . Constant space is used.
Algorithm
Another way to find the number of unique elements is to traverse over all the elements of the given array and keep on putting the elements in a set. By the property of a set, it will contain only unique elements. At the end, we can count the number of elements in the set, given by, say . The value to be returned will again be given by , as discussed in previous approaches. Here, refers to the size of the array.
Complexity Analysis
Time complexity : . The entire array is traversed only once. Here, refers to the size of array.
Space complexity : . will be of size in the worst case.
Analysis written by: @vinod23