SMOL_MISSIN - Editorial

editorial
,
1

PROBLEM LINK:

Practice

Author: Kunal Demla

DIFFICULTY:

MEDIUM

PREREQUISITES:

Arrays

PROBLEM:

Given an Array Arr return the minimum positive integer missing from the array.

QUICK EXPLANATION:

Set all Positive Integers i < N at Arr[i-1] and let all others be at random empty places. Traverse and output the 1st place where Arr[i-1]!=i.

EXPLANATION:

Completely sorting the array with any sorting algorithm takes at least O(N*log(N)) time complexity.
To solve the question in O(N),
We can conclude that it is viable to ignore any negative elements or any repetitive elements present in the array. We only need to deal with 1\leq Arr[i] \leq N However, since the inputs are very large, it is not feasible to use a hash map.
Therefore, we traverse the array while swapping, and keeping the value of Arr[i] the index Arr[i]-1 if 1 \leq Arr[i] \leq N and Arr[Arr[i]-1] is not already equals to Arr[i].
After traversing the whole array, start traversing from 0 and output where Arr[i-1]!=i.
If no such index is found, it can be concluded that all positive integers up till N exist in the array, hence output N+1.

SOLUTIONS:

Setter's Solution 
#include<bits/stdc++.h>
using namespace std;
#define ll long long int

void solve()
{
    ll n,x,y,i,j;
    cin>>n;
    vector<int> a(n);
    for(i=0;i<n;i++)
        cin>>a[i];
    for(i=0;i<n;i++)
    {
        while(a[i]>0 && a[i]<n && a[a[i]-1]!=a[i])
        {
            swap(a[i],a[a[i]-1]);
        }
    }
    for(i=0;i<n;i++)
    {
        if(a[i]!=i+1)
        {
            cout<<i+1;
            return;
        }
    }
    cout<<n+1;
}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("error.txt", "w", stderr);
freopen("output.txt", "w", stdout);
#endif

int t=1;
// ${2:is Single Test case?}cin>>t;
cin>>t;
while(t--)
{
    solve();
    cout<<"\n";
}

cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" secs"<<endl;
return 0;
}
2

You’ve got some complicated numerical thing going on but you really just need a (large) boolean array to say if you’ve seen a particular in-range entry or not.

for _ in range(int(input())):
    N = int(input())
    need = [True]*(N+2) # add zero, add N+1
    need[0] = False
    for ai in map(int, input().split()):
        if 0 < ai <= N:
            need[ai] = False
    for ht, req in enumerate(need):
        if req:
            print(ht)
            break