🔗 Ponketmon

After a long journey to catch Ponketmon, you arrive at Dr. Hong's laboratory. Dr. Hong tells you that you may take N/2 of the total N Ponketmon in his lab. The Ponketmon in Dr. Hong's lab are distinguished by a number assigned according to their species. So Ponketmon of the same species share the same number. For example, if there are a total of 4 Ponketmon in the lab, with species numbers [No. 3, No. 1, No. 2, No. 3], this means there are two No. 3 Ponketmon, one No. 1 Ponketmon, and one No. 2 Ponketmon. In this case, there are 6 ways to choose 2 out of the 4 Ponketmon, as follows.

1. Choose the 1st (No. 3) and 2nd (No. 1) Ponketmon
2. Choose the 1st (No. 3) and 3rd (No. 2) Ponketmon
3. Choose the 1st (No. 3) and 4th (No. 3) Ponketmon
4. Choose the 2nd (No. 1) and 3rd (No. 2) Ponketmon
5. Choose the 2nd (No. 1) and 4th (No. 3) Ponketmon
6. Choose the 3rd (No. 2) and 4th (No. 3) Ponketmon

Here, choosing the 1st (No. 3) and 4th (No. 3) Ponketmon gives you only one species (two No. 3 Ponketmon), while all the other choices give you two species. So in the example above, the maximum number of species you can have is 2.

Since you want to have as many different species of Ponketmon as possible, you want to choose N/2 Ponketmon that include as many species as possible. Given an array nums containing the species numbers of the N Ponketmon, complete the solution function so that it finds the way of choosing N/2 Ponketmon that includes the most species, and returns the number of species in that case.

• nums is a 1-dimensional array containing the species numbers of the Ponketmon.
• The length (N) of nums is a natural number between 1 and 10,000, and is always given as an even number.
• Each Ponketmon's species number is a natural number between 1 and 200,000.
• Even if there are multiple ways to choose the most species of Ponketmon, you only need to return the single maximum number of species that can be chosen.

Input/Output Example #1

Same as the example in the problem description.

Input/Output Example #2

There are 6 Ponketmon, so you must choose 3 Ponketmon. To choose the most species, pick one No. 3 Ponketmon, one No. 2 Ponketmon, and one No. 4 Ponketmon, so return 3.

Input/Output Example #3

There are 6 Ponketmon, so you must choose 3 Ponketmon. To choose the most species, pick one No. 3 Ponketmon and two No. 2 Ponketmon, or two No. 3 Ponketmon and one No. 2 Ponketmon. So the maximum number of species you can choose is 2.

You can take half, N / 2, of the N Ponketmon. This is an algorithm that asks for the number of species when you choose N / 2 out of N Ponketmon in the way that includes the most species.

It might look complicated at first glance, but it's actually quite simple once you think about it a bit.

If there are N Ponketmon that are all of different species, the maximum number of species you can obtain is N / 2.

On the other hand, if there are N Ponketmon but only two species, the maximum number of species you can obtain is capped at 2.

In other words, you just need to return the smaller of the number of species in the Ponketmon array nums and nums.length / 2.

• [1, 2, 3, 4, 5, 1] - there are 5 species, and N / 2 is 3, so the maximum number of species you can take is 3
• [1, 1, 1, 1, 2, 2, 3, 3] - there are 3 species, and N / 2 is 4, so the maximum number of species you can take is 3

It seems appropriate to use a HashSet, which only stores unique values, to find the number of species.

Insert the Ponketmon into a HashSet to get the number of species, compare it with array length / 2, and return the smaller value.

JAVA
/**
 * Ponketmon class
 *
 * @author RWB
 * @since 2021.12.11 Sat 01:56:08
 */
class Solution
{
	/**
	 * Method that returns the answer
	 *
	 * @param nums: [int[]] array of Ponketmon species
	 *
	 * @return [int] the number of species
	 */
	public int solution(int[] nums)
	{
		HashSet<Integer> set = new HashSet<>();
		
		for (int num : nums)
		{
			set.add(num);
		}
		
		return Math.min(set.size(), nums.length / 2);
	}
}