Số nguyên dương nhỏ nhất còn thiếu

Buổi 03 — Mảng 1 Chiều
Points
17
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
array1d
Submissions
Đề bài

Cho mảng số nguyên $A$ gồm $n$ phần tử (có thể chứa số âm, số $0$ và các số trùng lặp). Hãy tìm số nguyên dương nhỏ nhất (từ $1$ trở lên) không xuất hiện trong mảng $A$.

Dữ liệu vào

Dòng đầu chứa số nguyên $n$. Dòng thứ hai chứa $n$ số nguyên $A_1, A_2, \dots, A_n$.

Dữ liệu ra

Một số nguyên dương duy nhất là số nhỏ nhất còn thiếu.

Ví dụ

Input

4
3 4 -1 1

Output

2
Giới hạn

$1 \le n \le 10^5$, $|A_i| \le 10^9$. Yêu cầu thời gian $O(n)$ và bộ nhớ phụ $O(1)$.

Draft saved