Q6. Alice has n candies, where the ith candy is of type candyType[i]. Alice noticed that she started to gain weight, so she visited a doctor.

The doctor advised Alice to only eat n / 2 of the candies she has (n is always even). Alice likes her candies very much, and she wants to eat the maximum number of different types of candies while still following the doctor's advice.

Given the integer array candyType of length n, return the maximum number of different types of candies she can eat if she only eats n / 2 of them.

Intuition Behind the Algorithm

The "Distribute Candies" problem focuses on maximizing the variety of candies Alice can eat, subject to a dietary restriction. The essence of the solution lies in balancing two constraints: the total number of candies Alice can consume (half of her total candies, n / 2), and the variety of candy types available. The algorithm aims to identify the maximum number of unique candy types Alice can enjoy, ensuring diversity in her diet without exceeding the prescribed limit.

#include <vector>
#include <unordered_map>
using namespace std;

// Function to find the maximum number of different types of candies Alice can eat
int distributeCandies(vector<int>& candies) {
    // Create an unordered_map to store the frequency of each type of candy
    unordered_map<int, int> m;
    // Variable to keep count of the number of unique candies
    int count = 0;
    
    // Iterate over the candies vector
    for(int i = 0; i < candies.size(); i++) {
        // Check if the candy type is already in the map
        if(m.find(candies[i]) == m.end()) {
            // If not, add the candy type to the map and increment the unique candy count
            m.insert({candies[i], 1});
            count++;
        } else {
            // If the candy type is already in the map, increment its count
            m[candies[i]]++;
        }
    }
    
    // Calculate the maximum number of different types of candies Alice can eat
    // It is the minimum of the number of unique candies and n / 2
    int ans = count < candies.size() / 2 ? count : candies.size() / 2;
    return ans;
}

Code Walkthrough

The C++ solution uses an unordered_map to track the frequency of each candy type. This map serves as a counter for different types of candies, ensuring each type is counted only once.

• Initialization: An unordered_map (m) and a count variable are initialized. The map stores candy types and their occurrences, while count tracks the number of unique candies.

• Candy Counting Loop: Iterating through the candies vector, the algorithm checks if a candy type is already in the map. If not, it adds the new candy type to the map and increments count. This step effectively counts unique candy types.

• Calculating the Answer: The final step involves a comparison: if the count of unique candies is less than n / 2, Alice can eat all unique types. Otherwise, she is limited to n / 2 types. The ans variable is set to the smaller of these two values, representing the maximum variety she can achieve.

Time and Space Complexity Analysis

• Time Complexity: The algorithm iterates once over the candies vector of size n, leading to a time complexity of O(n). The operations inside the loop (map insertion/check) operate in average constant time due to the nature of unordered_map.

• Space Complexity: The space complexity is O(n) in the worst case, when all candy types are unique, requiring an entry in the map for each candy.

Key Points of the Algorithm

• Efficient Counting: Using an unordered_map enables efficient counting of unique candy types.
• Balancing Constraints: The algorithm successfully balances the two constraints – the limit on the number of candies and the desire for maximum variety.
• Scalability: The solution scales linearly with the number of candies, making it effective for large datasets.

Conclusion

The presented solution effectively solves the problem with linear time and space complexity. For further optimization, one might consider early termination of the loop if the count of unique candies reaches n / 2 before the end of the array, as any additional unique candies wouldn't increase the maximum variety Alice can achieve.