At a weekend music festival, wristbands are printed at a single kiosk before doors open. The printer numbers wristbands sequentially starting at 1, but as a safety backup the very last (highest) number in a batch is always printed onto two separate wristbands -- one for the guest, one for the gate captain's duplicate ledger. A gate scanner records the numbers on every wristband it scans during entry, but scans can arrive in any order, and the operator wants to confirm the reader actually saw one complete, unmodified printer batch (and not a mix of batches, a missing wristband, or a forged duplicate).
Given the multiset of scanned numbers, decide whether it forms exactly one valid batch: a permutation of 1, 2, ..., k-1, k, k for some integer k >= 1 (every value from 1 to k-1 appears exactly once, and k itself appears exactly twice).
Line 1: a single integer m -- the number of wristbands scanned. Line 2: m space-separated integers, the scanned wristband numbers.
Print true if the scanned numbers form exactly one valid printer batch, otherwise print false.
1 <= m <= 100000 1 <= scanned number <= 200000
Example 1
Input
2 1 1
Expected
true
Explanation
With k=1, the only valid batch is [1,1] -- there are no numbers below k, and the highest number 1 is duplicated. The scan matches this exactly, so the answer is true.
Example 2
Input
3 2 2 2
Expected
false
Explanation
For m=3 the only possible valid batch has k=2, i.e. one wristband numbered 1 and two numbered 2 ([1,2,2]). The gate instead scanned three wristbands all numbered 2 -- missing the required 1 and with one extra 2 -- so it cannot be a valid batch and the answer is false.
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 →