**Problem :- **

Find the smallest positive element missing in the given array of size **'n'** consisting of both positive & negative integers.

Consider the array ** { -8, 3, 2, -4, 6, 1, 5 } **.

Smallest positive element missing in the array is **4**.

**Solution :- **

We might think of an approach in which we start searching the array for positive integers starting from **1** and look
for the first missing element. This is a very
inefficient approach.

We can also use **hash table** where positive integers are the **keys** and **values** denote their presence in
the array. If a value **'x'** is present, **hash_map[x]** is set to 1, else 0. Then we traverse the **hash_map** to look
for first **key** with **value** set to **0**.

This is efficient in terms of time **complexity** but not so efficient
if we consider the space **complexity**.

We will go for an approach best in terms of both time and space **complexity**.

First let's divide the array in two halves. First half consisting of negative elements only & 2nd half consisting of positive elements.
This can be done with the same logic discussed in sorting an array of **0**s & **1**s.

Then we consider the positive half of the array and find the smallest missing element extending the logic discussed in
find duplicate elements in the array.

If we see element **'x'**, we make the element at **pos_half(x)** negative.

Then we traverse the positive half again to look for 1st negative value. The index of that value is the smallest positive element missing
in the array. See the implementation below.

**#include<iostream>
#include<cmath>**
**using namespace** std;
*// swap elements of two indexes in the array*
**void** swap (**int** arr[], **int** pos1, **int** pos2) {
**int** temp = arr[pos1];
arr[pos1] = arr[pos2];
arr[pos2] = temp;
}
*// classfies the postive and non-positive elements
// into two sections within the array
// sample i/p :: 7,-8,57,6,0,1,19,-4,-7,2
// sample o/p :: -7 -4 -8 0 6 1 19 57 7 2
// returns the index of the first positive element*
**int** classifyPosNeg(**int** arr[],**int** size) {
**int** j = size-1;
**int** i = 0;
*// start traversing the array from end*
**while** (j >= i ) {
**if** (arr[j] <= 0) {
*// move the non-positive no.s to the portion of
// array where all non-pos no. are present and
// increase their boundary towards right*
swap(arr,i,j);
i++;
}
**else** {
*// don't do anything if pos no. is found*
j--;
}
}
**return** i;
}
*// finds the smallest positive element which is missing in the
// given array*
**int** findSmallestMissingPosElement(**int** arr[],**int** size) {
*// classify the elements into two portions
// get the index of first pos element*
**int** pos_start = classifyPosNeg(arr,size);
arr = arr + pos_start; *// shift the array*
size = size - pos_start; *// update the new array size*
**int** i;
**for** (i=0;i<size;i++) {
**int** k = abs(arr[i]);
*// 'k-1' since array index starts at 0*
**if** (arr[k-1] > 0 && (k-1) < size) {
*// mark the element 'k' as present by
// negating the value at index k-1*
arr[k-1] = -arr[k-1];
}
}
*// look for the first positive value in the shifted array*
**for** (i=0;i<size;i++) {
**if** (arr[i] > 0) {
*// implies i+1 was not seen in the array
// so 'i+1' is missing*
**return** i+1;
}
}
**return** size+1;
}
*// main*
**int** main() {
**int** arr[] = {7,-8,57,6,0,1,19,-4,-7,2};
**int** size = **sizeof**(arr)/**sizeof**(arr[0]);
**int** missing_element = findSmallestMissingPosElement(arr,size);
cout<<"\nSmallest Positive missing element is "<<missing_element;
cout<<endl;
**return** 0;
}