A trade-show organizer has a bin of n free product samples left over after the event (n is guaranteed to be even). Each sample is stamped with an integer product-line code. The samples must be split evenly between two booths, Booth A and Booth B, so that each booth ends up with exactly n/2 samples (the organizer is free to choose which samples go where). The organizer wants Booth A's half to showcase as many different product lines as possible, and asks you to compute the maximum number of distinct product-line codes that can appear among Booth A's n/2 samples.
Line 1: a single even integer n, the total number of samples. Line 2: n space-separated integers, the product-line code of each sample.
A single integer: the maximum number of distinct product-line codes Booth A can receive.
Example 1
Input
6 1 1 2 2 3 3
Expected
3
Explanation
There are 3 distinct product-line codes (1, 2, 3) and Booth A gets 6/2 = 3 samples, so Booth A can get one of each: 3 distinct codes.
Example 2
Input
4 1 1 2 3
Expected
2
Explanation
There are 3 distinct codes but Booth A only receives 4/2 = 2 samples, so at most 2 distinct codes fit in Booth A's half, e.g. codes 1 and 2.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →