Let $cnt$ be an integer array of length 10^5. For each value $x$ from the input list of repressed individuals, set cnt[x] = 1.

Then we need to find the smallest index $i$ for which cnt[i] = 0. This number is the smallest one that does not appear in the input data. This $i$ will be the number of the most talented military officer among those who survived.

Example

Let us look at the state of the $cnt$ array after processing all the data from the input test.

The smallest number missing from the input array is $5$, because cnt[5] = 0.

Algorithm implementation

Declare an array to keep track of the numbers that appear in the input data.

#define MAX 100001
int cnt[MAX];

Read the input data. For each value $x$ from the list of repressed individuals, set cnt[x] = 1.

scanf("%d", &n);
for (i = 0; i < n; i++)
{
  scanf("%d", &x);
  cnt[x] = 1;
}

Next, search for the smallest non-negative integer that is missing from the input list. To do this, we need to find the smallest i~(i \ge 0) such that cnt[i] = 0.

for (i = 0; i < MAX; i++)
  if (cnt[i] == 0)
  {
    printf("%d\n", i);
    break;
  }

Algorithm implementation – bitset

Declare the constant $MAX$ and the bit array $m$.

#define MAX 100001
bitset<MAX> m;

Read the input data. For each value $x$ from the list of repressed individuals, set m[x] = true.

scanf("%d", &n);
for (i = 0; i < n; i++)
{
  scanf("%d", &x);
  m[x] = true;
}

Next, search for the smallest non-negative integer that is missing from the input list. To do this, we need to find the smallest i~(i \ge 0) such that m[i] = 0.

for (i = 0; i < MAX; i++)
  if (!m[i])
  {
    printf("%d\n", i);
    return 0;
  }