Условие

У Алисы есть n конфет, где i-я конфета имеет тип candyType[i]. Алиса заметила, что начала набирать вес, поэтому обратилась к врачу.

Врач посоветовал Алисе съедать только n/2 из имеющихся у неё конфет (n всегда чётное). Алиса очень любит свои конфеты и хочет съесть максимальное количество различных типов конфет, соблюдая рекомендации врача.

Верните максимальное количество различных типов конфет, которые Алиса может съесть, если она съест только n/2 из них.

Примеры

Input: candyType = [1, 1, 2, 2, 3, 3] Output: 3 Explanation: Алиса может съесть 6 / 2 = 3 конфеты. Поскольку существует только 3 типа, она может съесть по одной конфете каждого типа.

Input: candyType = [1, 1, 2, 3] Output: 2 Explanation: Алиса может съесть 4 / 2 = 2 конфеты. Независимо от того, какие типы она выберет — [1,2], [1,3] или [2,3] — она сможет съесть только 2 различных типа.

Input: candyType = [6, 6, 6, 6] Output: 1 Explanation: Алиса может съесть 4 / 2=2 конфеты. Однако существует только 1 тип конфет.

Решение

fun distributeCandies(candyType: IntArray): Int {
    // Используем HashSet для хранения уникальных типов конфет
    val uniqueCandyTypes = HashSet<Int>()

    // Заполняем множество уникальными типами конфет
    for (candy in candyType) {
        uniqueCandyTypes.add(candy)
    }

    // Максимальное количество конфет, которое Алиса может съесть
    val maxCandiesAliceCanEat = candyType.size / 2

    // Возвращаем минимальное значение между количеством уникальных типов и максимальным количеством конфет
    return minOf(uniqueCandyTypes.size, maxCandiesAliceCanEat)
}

Временная сложность

O(n), где n — длина массива candyType. Мы проходим по массиву, чтобы добавить элементы в HashSet.

Пространственная сложность

O(k), где k — количество уникальных типов конфет. Это связано с хранением уникальных элементов в HashSet.