Skip to content

1144 The Missing Number

Statement

Metadata

  • 作者: CHEN, Yue
  • 单位: 浙江大学
  • 代码长度限制: 16 KB
  • 时间限制: 200 ms
  • 内存限制: 64 MB

Given N integers, you are supposed to find the smallest positive integer that is NOT in the given list.

Input Specification

Each input file contains one test case. For each case, the first line gives a positive integer N (\le 10^5). Then N integers are given in the next line, separated by spaces. All the numbers are in the range of int.

Output Specification

Print in a line the smallest positive integer that is missing from the input list.

Sample Input 

10
5 -25 9 6 1 3 4 2 5 17

Sample Output 

7

Solution

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, b[N];

int main() {
    while (scanf("%d", &n) != EOF) {
        memset(b, 0, sizeof b);
        for (int i = 1, x; i <= n; ++i) {
            scanf("%d", &x);
            if (x >= 1 && x <= 100005) {
                b[x] = 1;
            }
        }
        for (int i = 1; i <= 100006; ++i) {
            if (b[i] == 0) {
                printf("%d\n", i);
                break;
            }
        }
    }
    return 0;
}
Last update: May 4, 2022
Back to top