Maximum types of candies a person can eat if only N/2 of them can be eaten (Distribute Candies)
Given an array arr[] of N candies, with N being an even number and arr[i] representing the type of candy. The task is to find the maximum number of different types of candies a person can eat if only N/2 of them can be eaten.
Examples:
Input: arr[] = {4, 4, 5, 5, 6, 6, 7, 7}
Output: 4
Explanation: Person can only eat 8/2 = 4 candies and there are 4 types of candies in the array. Thus, the person can eat one candy of each type.Input: arr[] = {2, 2, 3, 1}
Output: 2
Explanation: Person can only eat 4/2 = 2 and there are 3 types of candies in the array. Thus, the answer is 2, since maximum 2 candies allowed.
Naive Approach: The idea is to find the number of candy types in the given array. If the maximum number of candies that are allowed to eat is greater than the given number of candy types, then the answer is the number of candy types given. Else, the answer is the maximum number of candies that are allowed to eat.
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The idea is to use hashing. Follow the steps below to solve the problem:
- Initialize a hashset s to store the unique candy types.
- Traverse the array, arr[] and insert all the elements in the set, s.
- Store the size of the hashset s, in a variable M.
- If the value of (M < N/2), then print M, else print N/2 as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find number of candy types int num_candyTypes(vector< int >& candies) { // Declare a hashset to store candies unordered_set< int > s; // Traverse the given array and // inserts element into set for ( int i = 0; i < candies.size(); i++) { s.insert(candies[i]); } // Return the result return s.size(); } // Function to find maximum number of // types of candies a person can eat void distribute_candies(vector< int >& candies) { // Store the number of candies // allowed to eat int allowed = candies.size() / 2; // Store the number of candy types int types = num_candyTypes(candies); // Return the result if (types < allowed) cout << types; else cout << allowed; } // Driver Code int main() { // Given Input vector< int > candies = { 4, 4, 5, 5, 3, 3 }; // Function Call distribute_candies(candies); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find number of candy types public static int num_candyTypes( int []candies) { // Declare a hashset to store candies Dictionary<Integer, Integer> s = new Hashtable<Integer, Integer>(); // Traverse the given array and // inserts element into set for ( int i = 0 ; i < candies.length; i++) { s.put(candies[i], 1 ); } // Return the result return s.size(); } // Function to find maximum number of // types of candies a person can eat public static void distribute_candies( int []candies) { // Store the number of candies // allowed to eat int allowed = candies.length / 2 ; // Store the number of candy types int types = num_candyTypes(candies); // Return the result if (types < allowed) System.out.println(types); else System.out.println(allowed); } // Driver code public static void main(String[] args) { // Given Input int candies[] = { 4 , 4 , 5 , 5 , 3 , 3 }; // Function Call distribute_candies(candies); } } // This code is contributed by mohit kumar 29 |
Python3
# python 3 program for the above approach # Function to find number of candy types def num_candyTypes(candies): # Declare a hashset to store candies s = set () # Traverse the given array and # inserts element into set for i in range ( len (candies)): s.add(candies[i]) # Return the result return len (s) # Function to find maximum number of # types of candies a person can eat def distribute_candies(candies): # Store the number of candies # allowed to eat allowed = len (candies) / 2 # Store the number of candy types types = num_candyTypes(candies) # Return the result if (types < allowed): print ( int (types)) else : print ( int (allowed)) # Driver Code if __name__ = = '__main__' : # Given Input candies = [ 4 , 4 , 5 , 5 , 3 , 3 ] # Function Call distribute_candies(candies) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program for the above approach using System; using System.Collections.Generic; public class GFG{ // Function to find number of candy types public static int num_candyTypes( int []candies) { // Declare a hashset to store candies Dictionary< int , int > s = new Dictionary< int , int >(); // Traverse the given array and // inserts element into set for ( int i = 0; i < candies.Length; i++) { if (!s.ContainsKey(candies[i])) s.Add(candies[i], 1); } // Return the result return s.Count; } // Function to find maximum number of // types of candies a person can eat public static void distribute_candies( int []candies) { // Store the number of candies // allowed to eat int allowed = candies.Length / 2; // Store the number of candy types int types = num_candyTypes(candies); // Return the result if (types < allowed) Console.WriteLine(types); else Console.WriteLine(allowed); } // Driver code static public void Main (){ // Given Input int [] candies = { 4, 4, 5, 5, 3, 3 }; // Function Call distribute_candies(candies); } } // This code is contributed by unknown2108. |
Javascript
<script> // Javascript program for the above approach // Function to find number of candy types function num_candyTypes(candies) { // Declare a hashset to store candies let s = new Set(); // Traverse the given array and // inserts element into set for (let i = 0; i < candies.length; i++) { s.add(candies[i]); } // Return the result return s.size; } // Function to find maximum number of // types of candies a person can eat function distribute_candies(candies) { // Store the number of candies // allowed to eat let allowed = candies.length / 2; // Store the number of candy types let types = num_candyTypes(candies); // Return the result if (types < allowed) document.write(types); else document.write(allowed); } // Driver Code // Given Input let candies = [4, 4, 5, 5, 3, 3]; // Function Call distribute_candies(candies); // This code is contribute by gfgking. </script> |
3
Time Complexity: O(N)
Auxiliary Space: O(N)