Java Ponketmon: Why the Answer Is min(Distinct Types, N/2)

When selecting N/2 items from N to maximize distinct types, the answer is min(distinct types, N/2). You cannot select more types than items or invent types absent from the input.

The Ponketmon exercise supplies positive even N≤10,000 and type IDs from 1 to 200,000. It asks for one maximum count, not a particular selection.

Processing flow

Distinct types and the N/2 selection limit are both upper bounds. Their minimum is achievable under this exercise contract.

Count types with HashSet

Save this complete class as Solution.java. It was compiled for Java 11 and executed on JDK 17.

import java.util.HashSet;
import java.util.Set;

public class Solution {
    public int solution(int[] nums) {
        Set<Integer> kinds = new HashSet<>();
        for (int kind : nums) kinds.add(kind);
        return Math.min(kinds.size(), nums.length / 2);
    }
}

HashSet retains each ID once. Its size is the number of distinct types u, while k=nums.length / 2 is the number of available selection slots. Per-type frequencies are unnecessary here.

Show that the bound is achievable

If u≥k, select one item from each of k different types. If u<k, select one item from every type, then fill the remaining k-u slots with other items. Only u of the N items have been used, and k≤N, so enough remain. Thus the upper bound min(u, k) is achievable.

Input	Types u	Slots k	Answer
[3,1,2,3]	3	2	2
[3,3,3,2,2,2]	2	3	2
[7,7]	1	1	1

With appropriately dispersed hashes, expected time is O(N) and additional space O(u). Returning selected indices would require an additional construction procedure; this method only computes the count requested by the exercise.

For small inputs, checks compare against enumerating every selection of N/2 positions. Maximum-length checks cover 10,000 unique types and 10,000 copies of one type. These validate results without benchmarking hash implementation speed.

For a case where the number of duplicates matters, compare name frequencies for the missing runner.