Find the missing smallest positive number

Find the missing smallest positive number” is again one of the favorite 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:

INPUT:
Arr[10] = {-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 the missing smallest positive integer from the array. Some of them are:

METHOD 1: Brute-Force Solution

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 the missing smallest positive integer from the array is as follows:

/* C++ Program to find smallest positive integer 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 Based

This method is more time efficient than first 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 the missing smallest positive integer from the array is as follows:

/* C++ Program to find smallest positive integer 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];  
    }  
      
    /* 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

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *