A coffee shop wants to size a new "Gold" loyalty tier by picking a single cutoff number of stamps, x, such that exactly x of its n enrolled customers have collected at least x stamps -- that way the tier's own size and its entry requirement agree with each other. Note that x does not need to equal any customer's actual stamp count, and x is allowed to be 0.
Given how many stamps each customer has collected, find this cutoff x. It can be shown that if such a cutoff exists at all, it is unique.
Line 1: a single integer n -- the number of enrolled customers. Line 2: n integers s_0 s_1 ... s_{n-1}, the number of stamps customer i has collected.
Print the unique integer x such that exactly x customers have at least x stamps, or print -1 if no such x exists.
Example 1
Input
5 0 4 3 0 4
Expected
3
Explanation
Sorted, the stamp counts are 0, 0, 3, 4, 4. Checking each possible cutoff from 0 to 5: only x = 3 works, because exactly 3 customers (the ones with 3, 4, and 4 stamps) have at least 3 stamps, while every other cutoff in range produces a mismatched count. The answer is 3.
Example 2
Input
2 1 1
Expected
-1
Explanation
x = 0 would require 0 customers with at least 0 stamps, but both customers qualify (2 != 0). x = 1 would require exactly 1 customer with at least 1 stamp, but both customers qualify (2 != 1). x = 2 would require exactly 2 customers with at least 2 stamps, but neither customer qualifies (0 != 2). No cutoff in 0..2 works, so the answer is -1.
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 →