You have a collection of n trading cards, each stamped with a numeric identifier. You want to bind cards together into pairs, but a pair may only be formed from two cards that share the same identifier, and each card may be used in at most one pair.
Form as many such pairs as possible from the collection. Any cards that cannot be paired off are left as singles.
Given the identifiers of all n cards, report the maximum number of pairs that can be formed and the number of cards left unpaired after forming them.
Line 1: a single integer n, the number of cards.
Line 2: n space-separated integers id_1 ... id_n, the identifier stamped on each card.
Print two space-separated integers on one line: the number of pairs formed, followed by the number of cards left unpaired.
Example 1
Input
7 1 3 2 1 3 2 2
Expected
3 1
Explanation
Identifier 1 appears twice (1 pair), identifier 3 appears twice (1 pair), and identifier 2 appears three times (1 pair, with 1 card left over). That totals 3 pairs and 1 unpaired card, so the output is "3 1".
Example 2
Input
2 1 1
Expected
1 0
Explanation
Both cards share identifier 1, so they form exactly 1 pair with 0 cards left over. The output is "1 0".
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 →