# Find missing smallest positive number

Find missing smallest positive number” is again one of the favourite technical interview problem. Here, we are given an unsorted array of size ‘n’ and our task is to find the missing smallest positive number from the array. The array may contain both positive and negative integers.

Example (Find missing smallest positive number):

```INPUT:
Arr = {-2, 11, 3, -1, 2, 0, 4, 7, 90, 3}
OUTPUT:
1 is the smallest missing integer from the array```

There could be multiple ways to find missing smallest positive number from the array. Some of them are:

#### METHOD 1: Brute-Force Solutionto find missing smallest positive number

The most naïve solution of the given problem is to traverse the given array and search the elements from 1 to N. If there is any element from 1 to N, which is missing, then it would be resultant element.

If all the elements from 1 to N are present, then (N+1) would be resultant element.

Here, in worst case, the time complexity would be O(n^2).

#### C++ Program to find missing smallest positive number in an array is as follows:

```/* C++ Program to find missing smallest positive number of the array */
#include<bits/stdc++.h>
using namespace std;
int main()
{
/* Scan size of array */
int n;
cout<<"Enter the size of the array:";
cin>>n;

/*Scan array elements */
int arr[n];
cout<<"\nEnter the array elements:";
for(int i = 0; i < n; i++)
{
cin>>arr[i];
}

/* Finding the smallest positive integer */

/* In case, we found all the elements from 1 to n,
(n+1) would the smallest missing positive integer */
int res = n+1;
for(int i = 1; i <= n; i++)
{
int flag = 0;
for(int j = 0; j < n; j++)
{
if(arr[j] == i)
{
flag = 1;
break;
}
}
/* If we found any element, which is missing from 0 to n,
then that element would be the resulant element */
if(flag == 0)
{
res = i;
break;
}
}
cout<<"\n"<<res<<" is the smallest missing positive integer";
}

```
```OUTPUT:
Enter the size of the array: 9
Enter the array elements: -2 -3 0 1 3 -5 5 9 10
2 is the smallest missing positive integer```

#### METHOD 2: Sorting Basedto find missing smallest positive number

This method is more time efficient than previous method. Here, we sort the given array in O(nlogn) time complexity and then linearly search element from 1 to N in a sorted array.

If all elements are present from 1 to N in sorted array, then (N+1) would be resultant element.

The time complexity of this solution would be O(nlogn), based on the type of sorting algorithm used.

#### C++ Program to find missing smallest positive number in an array is as follows:

```/* C++ Program to find missing smallest positive number in an array */
#include<bits/stdc++.h>
using namespace std;
int main()
{
/* Scan size of array */
int n;
cout<<"Enter the size of the array:";
cin>>n;

/*Scan array elements */
int arr[n];
cout<<"\nEnter the array elements:";
for(int i = 0; i < n; i++)
{
cin>>arr[i];
}

/* Sort the given array using in-built function */
sort(arr,arr+n);

/* Finding the smallest positive integer */
int res = 1;
for(int i = 0; i < n; i++)
{
/* Only positive integer needs to be find */
if(arr[i] > 0)
{
/* If we found the smallest integer, we would increment it */
if(arr[i] == res)
{
res ++;
}
/* Else that would be the resultant element */
else
{
break;
}
}
}

/* Printing the result */
cout<<"\n"<<res<<" is the smallest missing positive integer";
}

```
```OUTPUT:
Enter the size of the array: 9
Enter the array elements: 1 -1 2 3 -3 4 -4 10 8
2 is the smallest missing positive integer```

Related Posts: