Task 76. Перестановка массива

Задача: дан массив из N натуральных чисел. Необходимо определить, является ли он перестановкой первых N натуральных чисел.

Входные данные: массив из N натуральных чисел, где N <= 10000.

Вывод: Вывести 0, если массив является перестановкой, в противном случае вывести минимальное число, не входящее в эту последовательность.

Пример:

1. Arr = [ 1, 4, 2, 5, 6 ]

Вывод: 3

2. Arr = [ 1, 4, 2, 5, 6, 3 ]

Вывод: 0

Идея: есть несколько вариантов решения этой задачи, но один из самых простых это через использование 'хэш-функции'. В нашем случае мы создадим вспомогательный массив m и занесем в ячейку m[i] кол-во чисел i во входном массиве.

Если все значения m[1], m[2], ..., m[N] будут ненулевыми, то все эти значения больше 1 и на выходе мы имеем перестановку. В противном случае выводим наименьшее i, для ктр m[i] нулевое.

Реализация:

https://gist.github.com/unilecs/d3183d5bbf2a8f8d7b0b733b85c98eb7

Тест:

https://dotnetfiddle.net/q9sUMm