Distribute Candies

🏠 ⬅️ ➡️

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.

Example 1:

Input: candyType = [1,1,2,2,3,3] Output: 3 Explanation: Alice can only eat 6 / 2 = 3 candies. Since there are only 3 types, she can eat one of each type.

Example 2:

Input: candyType = [1,1,2,3] Output: 2 Explanation: Alice can only eat 4 / 2 = 2 candies. Whether she eats types [1,2], [1,3], or [2,3], she still can only eat 2 different types.

Example 3:

Input: candyType = [6,6,6,6] Output: 1 Explanation: Alice can only eat 4 / 2 = 2 candies. Even though she can eat 2 candies, she only has 1 type.

Constraints:

  • n == candyType.length
  • 2 <= n <= 104
  • n is even.
  • -105 <= candyType[i] <= 105
Note: This problem is from LeetCode.
✅ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer :: n, i
    integer, allocatable :: candyType(:)
    integer :: maxTypes

    ! read input
    read(*,*) n
    allocate(candyType(n))
    do i = 1, n
        read(*,*) candyType(i)
    end do

    ! solve problem
    maxTypes = solve(n, candyType)

    ! print output
    write(*,*) maxTypes

contains

    function solve(n, candyType) result(maxTypes)
        implicit none
        integer, intent(in) :: n
        integer, intent(in) :: candyType(:)
        integer :: maxTypes
        integer :: i, j, count

        maxTypes = 0
        do i = 1, n - 1
            count = 0
            do j = i + 1, n
                if (candyType(j) /= candyType(i)) then
                    count = count + 1
                end if
            end do
            maxTypes = max(maxTypes, count)
        end do
    end function solve

end program main
❌ Compiled
❌ Executed
❌ Correct 
module MaxCandyTypes
    implicit none
    private
    public :: max_candy_types
contains
    function max_candy_types(candy_type) result(max_types)
        integer, intent(in) :: candy_type(:)
        integer :: max_types
        integer :: i, j, n, count
        logical :: seen(size(candy_type))

        n = size(candy_type)
        max_types = 0
        count = 0
        seen = .false.

        do i = 1, n
            if (mod(i, 2) == 0) then
                if (.not. seen(candy_type(i))) then
                    count = count + 1
                    seen(candy_type(i)) = .true.
                end if
            end if
        end do

        max_types = count
    end function max_candy_types
end module MaxCandyTypes

program test_max_candy_types
    use MaxCandyTypes
    implicit none
    integer :: candy_type(6)

    candy_type = [1, 1, 2, 2, 3, 3]
    write (*, '(A, I0)') 'Max candy types: ', max_candy_types(candy_type)

    candy_type = [1, 1, 2, 3]
    write (*, '(A, I0)') 'Max candy types: ', max_candy_types(candy_type)

    candy_type = [6, 6, 6, 6]
    write (*, '(A, I0)') 'Max candy types: ', max_candy_types(candy_type)
end program test_max_candy_types
🌐 Data from online sources 
def maxNumberOfCandies(candyType):
    uniqueCandies = set(candyType)
    return min(len(uniqueCandies), len(candyType) // 2)

The algorithm starts by first creating a set of unique candy types using a hash set (in C++ and Java) or a set (in Python and JavaScript). The uniqueCandies set will only store each type of candy once, no matter how many times it appears in the candyType array. After creating this set, the algorithm compares the number of unique types of candies (size of the set) with half the total number of candies (n / 2). The minimum of these two values is returned as the maximum number of different types of candies Alice can eat. This is because Alice can eat at most n / 2 candies, but if there are fewer unique candies than that, she will eat all the unique types available.
🌐 Data from online sources 
#include <vector>
#include <unordered_set>
using namespace std;

int maxNumberOfCandies(vector<int>& candyType) {
    unordered_set<int> uniqueCandies(candyType.begin(), candyType.end());
    return min(uniqueCandies.size(), candyType.size() / 2);
}

The algorithm starts by first creating a set of unique candy types using a hash set (in C++ and Java) or a set (in Python and JavaScript). The uniqueCandies set will only store each type of candy once, no matter how many times it appears in the candyType array. After creating this set, the algorithm compares the number of unique types of candies (size of the set) with half the total number of candies (n / 2). The minimum of these two values is returned as the maximum number of different types of candies Alice can eat. This is because Alice can eat at most n / 2 candies, but if there are fewer unique candies than that, she will eat all the unique types available.