Số nguyên dương nhỏ nhất còn thiếu trong dãy
Khi cấp phát số thứ tự cho một tập dữ liệu nhỏ, ta muốn tìm số thứ tự còn trống đầu tiên để
Tiến độ của tôi ở bài này
Điểm và code bạn nộp được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: cpp-basics, arrays.
Nội dung đề bài
Mô tả bài toán
Khi cấp phát số thứ tự cho một tập dữ liệu nhỏ, ta muốn tìm số thứ tự còn trống đầu tiên để điền vào chỗ hổng. Dãy đầu vào rất ngắn và có thể chứa số âm, số 0 hoặc các giá trị lặp lại, nên chỉ cần đánh dấu sự có mặt là đủ.
Yêu cầu
Cho n số nguyên. Hãy tìm số nguyên dương nhỏ nhất (bắt đầu từ 1) không xuất hiện trong dãy và in số đó ra. Giá trị 0 và các số âm không được tính, còn các giá trị lặp lại chỉ tính là có mặt một lần.
Quy ước nộp bài
Nộp chương trình solution.cpp đọc dữ liệu từ stdin theo đúng định dạng trên và in ra stdout một số nguyên duy nhất là đáp án.
Input
- Dòng 1: số nguyên n (1 <= n <= 30).
- Dòng 2: n số nguyên a1 a2 ... an (-10000 <= ai <= 10000).
Output
Một số nguyên duy nhất: số nguyên dương nhỏ nhất không có trong dãy.
Ràng buộc
- Dãy không được sắp xếp sẵn và có thể lẫn số âm, số 0, giá trị trùng nhau.
- Với dãy n phần tử, đáp án luôn nằm trong khoảng 1..n + 1.
- Mỗi bộ dữ liệu chạy trong 1 giây.
Ví dụ 1
Input
4
1 2 0 -1
Output
3
Ví dụ 2
Input
3
3 4 5
Output
1
Giải thích
Dữ liệu vào:
Trong dãy có 1 và 2; hai giá trị 0 và -1 không phải số dương. Số dương nhỏ nhất còn thiếu là 3, nên in ra 3.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.
