You are given an array arr[] of N integers including 0. The task is to find the smallest positive number missing from the array.

You are given an array arr[] of N integers including 0. The task is to find the smallest positive number missing from the array.

You are given an array arr[] of N integers including 0. The task is to find the smallest positive number missing from the array.

Note Expected solution in O(n) time using constant extra space (don't use hash maps or sorting algorithms in your solution).

Example:

Input:

2

5

1 2 3 4 5

5

0 -10 1 3 -20

Output:

6

2

Explanation:

Testcase 1: Smallest positive missing number is 6.

Testcase 2: Smallest positive missing number is 2.

Here is a simple and easy solution using hashing:

// { Driver Code Starts
#include<bits/stdc++.h>

using namespace std;


// } Driver Code Ends


// Functio to find first smallest positive
// missing number in the array
int missingNumber(int arr[], int n) {

    if (n == 1 && arr[0] != 1)
        return 1;
    int l = * max_element(arr, arr + n);
    ++l;
    int mp[l];

    memset(mp, 0, sizeof(mp));
    for (int i = 0; i < n; ++i) {
        if (arr[i] > 0) {
            mp[arr[i]]++;
        }
    }
    for (int i = 1; i < l; ++i) {
        if (mp[i] == 0)
            return i;
    }
    return l;


}

// { Driver Code Starts.

int missingNumber(int arr[], int n);

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int arr[n];
        for (int i = 0; i < n; i++) cin >> arr[i];
        cout << missingNumber(arr, n) << endl;
    }
    return 0;
} // } Drive int arr[n];