Distribute Candies

easy

Last Updated - 10/09/2024

Problem Statement Solution 1: Hash Set Approach Solution 2: Frequency Map Approach Solution 3: Sorting Approach Solution 4: Using a Map for Counting Solution 5: Array Deduplication and Length Check Solution 6: Greedy Approach with Array Processing Solution 7: Using Filter for Uniqueness Solution 8: Using Reduce to Count Unique Types More Problems Solutions

Problem Statement

Aman has a collection of n candies, where each candy is identified by its type in the array candyType. Aman has been advised by his doctor to limit his candy consumption to exactly half of his total candy collection. The goal is to help Aman enjoy the maximum variety of candy types while adhering to this limitation.

Specifically, Aman wants to maximize the number of distinct candy types he can eat given that he can only consume n / 2 candies.

Example 1

Input: candyType = [1,1,2,2,3,3]

Output: 3

Example 2

Input: candyType = [1,1,2,3]

Output: 2

Example 3

Input: candyType = [6,6,6,6]

Output: 1

Constraints

n (length of candyType array) is an even integer within the range 2 <= n <= 10^4.
The integer values in candyType can range from -10^5 to 10^5.

Solution 1: Hash Set Approach

function distributeCandiesHashSet(candyType) {
    const uniqueTypes = new Set(candyType);
    const maxDistinctTypes = candyType.length / 2;
    return Math.min(uniqueTypes.size, maxDistinctTypes);
} 

const candyType1 = [1,1,2,2,3,3];
distributeCandiesHashSet(candyType1);  //output: 3 

const candyType2 = [1,1,2,3];
distributeCandiesHashSet(candyType2);  //output: 2 

const candyType3 = [6,6,6,6];
distributeCandiesHashSet(candyType3);  //output: 1

Solution 2: Frequency Map Approach

function distributeCandiesFrequencyMap(candyType) {
    const frequencyMap = {};
    candyType.forEach(candy => frequencyMap[candy] = (frequencyMap[candy] || 0) + 1);
    const distinctTypes = Object.keys(frequencyMap).length;
    const maxDistinctTypes = candyType.length / 2;
    return Math.min(distinctTypes, maxDistinctTypes);
} 

const candyType1 = [1,1,2,2,3,3];
distributeCandiesFrequencyMap(candyType1);  //output: 3 

const candyType2 = [1,1,2,3];
distributeCandiesFrequencyMap(candyType2);  //output: 2 

const candyType3 = [6,6,6,6];
distributeCandiesFrequencyMap(candyType3);  //output: 1

Solution 3: Sorting Approach

function distributeCandiesSorting(candyType) {
    const sortedTypes = [...new Set(candyType)].sort();
    const maxDistinctTypes = candyType.length / 2;
    return Math.min(sortedTypes.length, maxDistinctTypes);
} 

const candyType1 = [1,1,2,2,3,3];
distributeCandiesSorting(candyType1);  //output: 3 

const candyType2 = [1,1,2,3];
distributeCandiesSorting(candyType2);  //output: 2 

const candyType3 = [6,6,6,6];
distributeCandiesSorting(candyType3);  //output: 1

Solution 4: Using a Map for Counting

function distributeCandiesMapCounting(candyType) {
    const candyCountMap = new Map();
    candyType.forEach(candy => {
        if (!candyCountMap.has(candy)) {
            candyCountMap.set(candy, 1);
        }
    });
    const distinctTypes = candyCountMap.size;
    const maxDistinctTypes = candyType.length / 2;
    return Math.min(distinctTypes, maxDistinctTypes);
} 

const candyType1 = [1,1,2,2,3,3];
distributeCandiesMapCounting(candyType1);  //output: 3 

const candyType2 = [1,1,2,3];
distributeCandiesMapCounting(candyType2);  //output: 2 

const candyType3 = [6,6,6,6];
distributeCandiesMapCounting(candyType3);  //output: 1

Solution 5: Array Deduplication and Length Check

function distributeCandiesArrayDeduplication(candyType) {
    const uniqueTypes = Array.from(new Set(candyType));
    const maxDistinctTypes = candyType.length / 2;
    return Math.min(uniqueTypes.length, maxDistinctTypes);
} 

const candyType1 = [1,1,2,2,3,3];
distributeCandiesArrayDeduplication(candyType1);  //output: 3 

const candyType2 = [1,1,2,3];
distributeCandiesArrayDeduplication(candyType2);  //output: 2 

const candyType3 = [6,6,6,6];
distributeCandiesArrayDeduplication(candyType3);  //output: 1

Solution 6: Greedy Approach with Array Processing

function distributeCandiesGreedy(candyType) {
    const distinctTypes = new Set();
    let count = 0;
    for (const candy of candyType) {
        if (!distinctTypes.has(candy)) {
            distinctTypes.add(candy);
            count++;
        }
        if (count >= candyType.length / 2) {
            break;
        }
    }
    return Math.min(distinctTypes.size, candyType.length / 2);
} 

const candyType1 = [1,1,2,2,3,3];
distributeCandiesGreedy(candyType1);  //output: 3 

const candyType2 = [1,1,2,3];
distributeCandiesGreedy(candyType2);  //output: 2 

const candyType3 = [6,6,6,6];
distributeCandiesGreedy(candyType3);  //output: 1

Solution 7: Using Filter for Uniqueness

function distributeCandiesFilter(candyType) {
    const uniqueTypes = candyType.filter((value, index, self) => self.indexOf(value) === index);
    const maxDistinctTypes = candyType.length / 2;
    return Math.min(uniqueTypes.length, maxDistinctTypes);
} 

const candyType1 = [1,1,2,2,3,3];
distributeCandiesFilter(candyType1);  //output: 3 

const candyType2 = [1,1,2,3];
distributeCandiesFilter(candyType2);  //output: 2 

const candyType3 = [6,6,6,6];
distributeCandiesFilter(candyType3);  //output: 1

Solution 8: Using Reduce to Count Unique Types

function distributeCandiesReduce(candyType) {
    const uniqueTypes = candyType.reduce((acc, candy) => {
        if (!acc.includes(candy)) {
            acc.push(candy);
        }
        return acc;
    }, []);
    const maxDistinctTypes = candyType.length / 2;
    return Math.min(uniqueTypes.length, maxDistinctTypes);
} 

const candyType1 = [1,1,2,2,3,3];
distributeCandiesReduce(candyType1);  //output: 3 

const candyType2 = [1,1,2,3];
distributeCandiesReduce(candyType2);  //output: 2 

const candyType3 = [6,6,6,6];
distributeCandiesReduce(candyType3);  //output: 1