A lakeside outfitter has n guests waiting for tandem kayaks, where n is always even. To keep every kayak balanced, the dock master repeatedly pairs the heaviest remaining guest with the lightest remaining guest, records the average of their two weights, and sends the pair off to their kayak; this continues until every guest has been paired exactly once. Determine how many distinct average weights appear across all the pairs formed.
The first line contains a single integer n, the number of guests. The second line contains n integers, the weights of the guests in kilograms, separated by spaces.
Print a single integer: the number of distinct average weights among the pairs formed.
Example 1
Input
6 4 1 4 0 3 5
Expected
2
Explanation
Sorted, the weights are [0, 1, 3, 4, 4, 5]. Pairing lightest with heaviest each round gives (0,5) averaging 2.5, (1,4) averaging 2.5, and (3,4) averaging 3.5. The distinct averages are 2.5 and 3.5, so the answer is 2.
Example 2
Input
2 1 100
Expected
1
Explanation
There is only one pair, (1, 100), with average 50.5, so there is exactly 1 distinct average.
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 →