Ants
InterviewTime limit2sMemory limit512 MB
Given N integers, some negative or very large, find the smallest nonnegative integer that does not appear among the valid nonnegative values.
- Level
Medium4 of 10
- Topics
- Array, Hash map, Sorting, Implementation
- Solved
- No attempts yet
Problem
Charles is fascinated by ants. To observe a colony of ants over a long period, Charles built a program that uniquely identifies each ant using image recognition. (Yes, every ant is unique.) Inside the program, each ant is tagged with a unique nonnegative integer. Whenever there is a birth in the colony, the new ant is given a new tag, different from all tags already assigned. Whenever some ant disappears, its tag falls back into the pool of available tags.
Charles's program works as follows. It first scans the whole colony, building the list of tags of the ants that are recognized. Then it assigns fresh tags to the new ants. To do so, the program simply picks the first natural number (that is, nonnegative integer) that is not currently assigned to any ant, and so on.
Due to some glitches in the image recognition device and in the program, there are sometimes negative or very large numbers that appear in the input list. These are simply ignored by Charles's program.
Your job is to reimplement the part of Charles's program that finds a fresh tag to assign to a new ant.
Input
The input consists of the following lines:
- on the first line: an integer N;
- on the next N lines: some integers X1, ..., XN, one per line.
Output
The smallest natural number that does not belong to the set {X1, ..., XN}.
Constraints
The input satisfies 0 ≤ N ≤ 106. Each integer Xi has less than 100 digits.