### PROBLEM LINK:

*Author:* Illisha Singh

*Tester:* Illisha Singh, Kabir Kanha Arora, Jackson Jose, Vaibhav Gautam, Nishank Suresh

*Editorialist:* Illisha Singh

### DIFFICULTY:

Easy

### PREREQUISITES:

### PROBLEM:

The key idea behind the solution is the fact that in an array of n numbers, the first missing natural number can be at most n+1, which is the case when the array itself contains all numbers 1 through n. In all other cases it would be some number in the range [1,n].

**Search for all natural numbers starting from 1** -

The most basic approach involves searching the array for all numbers starting from 1, all the way to n. If there is a number missing, print it else print n+1 as the answer.

This approach, however, would take O(n^2) time. Thus, it would not satisfy the constraints on n.

**Approach 1: A simple array based approach**

Since all numbers lie in the range [1,n], one can create an **array of size n** and initialise all its elements to 0. **Increment the count** of the elements of the array for each positive number in the input. Once this is done, a simple traversal to find the fist element with value 0 and printing it would suffice.

This approach too, takes up additional O(n) space and a linear search too, takes O(n) time.

**Approach 2: Sort and search the array**

Another way to solve the problem under the mentioned constraints would be by *sorting* using an algorithm that does so in O(nlogn) time. Once the array is sorted, a *linear search* would allow one to find the first missing natural number in linear time.

This approach would thus, take O(nlogn) + O(n) = O(nlogn) time.

**Approach 3: Use Hashing**

A convinient way would be to build a hash table of all *positive* elements in the given array.

Once a hashtable is successfully constructed, one can *search for all positive* integers, 1 onwards, there. As soon as one comes accross a number which is not present in the hash table, it is printed. And if all numbers, 1 through n are found in the table, n+1 is printed.

Hashing can be performed on n elements in O(n) time but with O(n) additional space.

### SOLUTIONS

## Setter's Solution (Approach1) - C++

```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll t;
cin >> t;
while (t--)
{
ll n;
cin >> n;
vector<ll> v(n);
for (auto &x : v)
{
cin >> x;
}
ll elementArray[n + 1] = {0};
for (ll i = 0; i < n; i++)
{
if (v[i] > 0 && v[i] <= n)
elementArray[v[i]] = 1;
}
ll flag = 0;
for (ll i = 1; i <= n; i++)
if (!elementArray[i])
{
cout<<i<<endl;
flag = 1;
break;
}
if(flag==0)
cout<<n+1<<endl;
}
return 0;
}
```

## Setter's Solution (Approach 2)- C++

```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll missingNum(vector<ll> &A)
{
ll ans;
ll flag=0;
if(A.size()==1)
{
if(A[0]>1||A[0]<0)
return 1;
else if(A[0]==1)
return 2;
}
sort(A.begin(),A.end());
for(int i=1; i<A.size()+1; i++)
{
bool r = binary_search(A.begin(), A.end(), i);
if(r==false)
{
ans = i;
flag=1;
break;
}
}
if(flag == 0)
return A.size()+1;
return ans;
}
int main()
{
ll t;
cin >> t;
while (t--)
{
ll n;
cin >> n;
vector<ll> v(n);
map<ll, bool> m;
for (auto &x : v)
{
cin >> x;
}
cout << missingNum(v) << endl;
}
return 0;
}
```

## Setter's Solution (Approach 3)- C++

```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll t;
cin >> t;
while (t--) {
ll n;
cin >> n;
vector<ll> v(n);
map<ll, bool> m;
for (auto &x : v) {
cin >> x;
if (x > 0) {
m[x] = true;
}
}
ll N = 1e5 + 1;
ll ans = 0;
for (ll i=1;i<=N;i++) {
if (m.count(i)== 0) {
ans = i;
break;
}
}
cout << ans << endl;
}
return 0;
}
```

## Tester Vaibhav's Solution(Approach 3)-Python

```
from collections import Counter
T=int(input())
while(T>0):
n = int(input())
A = [int(i) for i in input().split()]
d = Counter(A)
poss=False
for i in range(1, 100001):
if (d[i] == 0):
print(i)
poss=True
break
if(not poss):
print(n+1)
T-=1
```

## Tester Kabir's Solution (Approach 3) - Java

```
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int t = scanner.nextInt();
while (t-- > 0) {
int n = scanner.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; ++i) {
arr[i] = scanner.nextInt();
/*
Negative numbers ruin sorting order,
move them to the end by assigning a large value.
*/
if (arr[i] < 0) {
arr[i] = Integer.MAX_VALUE;
}
}
Arrays.sort(arr);
int missing = n + 1; // Default value is n+1, assuming nothing is missing.
// Find the first natural number that is missing in the array.
for (int i = 0; i < n; ++i) {
if (arr[i] != i + 1) {
missing = i + 1;
break;
}
}
System.out.println(missing);
}
}
}
```