ArrayCyclic SortHashing
Find the smallest positive integer (1, 2, 3, ...) that does not appear in the array. The array may contain negatives, zeros and duplicates. Aim for O(n) time and O(1) extra space.
Input
Line 1: n. Line 2: n integers.
Output
Print the smallest missing positive integer.
Constraints
1 <= n <= 10^5 -10^9 <= each value <= 10^9
Example 1
Input
3 1 2 0
Output
3
1 and 2 are present, so 3 is the first missing.
Example 2
Input
4 3 4 -1 1
Output
2
2 is the smallest positive integer that is absent.