Maximum types of candies a person can eat if only N/2 of them can be eaten (Distribute Candies)

0 0 4 minutes read

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(N²)
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>

Output

Time Complexity: O(N)
Auxiliary Space: O(N)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!