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);
}
}
}