A sequence of n
positive integers is given. Determine whether it is a permutation of the
first n positive integers.
Input. The first line
contains the integer n (n ≤ 10000), followed by a sequence
of n positive integers. It is known that each of these numbers
does not exceed 2 * 106.
Output. Print 0 if the
sequence is a permutation. Otherwise, print the smallest number that is missing
from the sequence.
|
Sample
input |
Sample
output |
|
3 1 4 2 |
3 |
counting sort
Declare the linear array m of length n ≤ 10000. Put the amount of numbers i
in the input sequence into cell m[i].
If all values m[1], m[2], …, m[n] are nonzero (there
are exactly n input numbers), then
all these values are equal to 1 and input seuence is a
permutation. Otherwise print the smallest i
for which m[i] is zero.
If some number of the input sequence is
greater than n, then such sequence is
not a permutation.
The number of input positive integers n is no more than 10000. Declare a
linear array.
#define MAX 10002
int m[MAX];
Read the input
data. Set all
elements of array m to zero.
scanf("%d",&n);
memset(m,0,sizeof(m));
For each input
number à ≤ n increase m[a] by one (a can take
values from 1 to 2000000).
for(i = 0; i < n; i++)
{
scanf("%d",&a);
if (a <=
n) m[a]++;
}
Find the
smallest positive
integer i, which is not
in the input array. For such number the equality m[i] = 0 holds.
for(i = 1; i <= n; i++)
if (m[i] ==
0) break;
If i > n, then all
numbers from 1 to n have met. So the
input sequence is a permutation. Otherwise i will be the
smallest number not included in this sequence.
if (i <= n) printf("%d\n",i); else
printf("0\n");
Java realization
import java.util.*;
public class Main
{
public static void
main(String[] args)
{
Scanner con = new
Scanner(System.in);
int i, n = con.nextInt();
int m[] = new int[n+1];
for(i = 0;
i < n; i++)
{
int a = con.nextInt();
if (a
<= n) m[a]++;
}
for(i = 1;
i <= n; i++)
if (m[i] ==
0) break;
if (i
<= n)
System.out.println(i);
else
System.out.println(0);
con.close();
}
}