Задана последовательность, состоящая из n натуральных чисел. Определить, является ли она перестановкой первых n натуральных чисел.
В единственной строке задано сначала число n (n ≤ 10000), а потом n натуральных чисел, разделенных пробелом. Известно, что каждое из натуральных чисел меньше 2000000.
Вывести 0, если последовательность является перестановкой. Иначе следует вывести минимальное число, не входящее в эту последовательность.
#include <iostream>
#include <string.h>
using namespace std;
int main() {
//Читаем входные данные. Обнуляем массив m. Для каждого входного числа
//а ? n увеличим m[a] на единицу (а может принимать значение от 1 до 2000000).
int a, n, i, m[10001];
scanf("%d", &n);
memset(m, 0, sizeof m);
for (i = 0; i < n; i++)
{
scanf("%d", &a);
if (a <= n) m[a]++;
}
//Находим наименьшее натуральное число i, которого нет во входном массиве.
//Для такого числа будет выполнено равенство m[i] = 0.
for (i = 1; i <= n; i++) if (m[i] == 0) break;
//Если i > n, то все числа от 1 до n встретились.
//Значит входная последовательность является перестановкой.
//Иначе i будет наименьшим числом, не входящим в эту последовательность
if (i <= n) printf("%d\n", i);
else printf("0\n");
return 0;
}
Есть решение которого нет на сайте? Пиши admin@devexe.top