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

Related Posts:

  1. Program to sort if array is sorted.
  2. Program to print Alternate Elements of an Array.
  3. Program to swap kth element from beginning to kth element from end in an Array.
  4. Program to print all possible subarrays of the given array.
  5. Program to print kth smallest and kth largest element of an Array.
  6. Program to find equilibrium index of an Array.
  7. Program to find majority element of an Array.
  8. Program to find mean of the Array.
  9. Program to sort an Array of 0s and 1s.
  10. Program to Reverse an Array.
  11. Program to count number of odd numbers and even numbers in an array.
  12. Program to find absolute difference between sum of odd index elements and even index elements.
  13. Program to find smallest and largest element of the array.
  14. Program to count occurrences of a particular element in an array.
  15. Program to search an element in an Array (Linear Search).
  16. Program to Rotate Array Elements by ‘D’ positions.
  17. Program to find most frequent element in an array.
  18. Program to find pair in an array with given sum.
  19. Program to find first repeating element of an array.
  20. Program to merge two sorted arrays.

You may also like...

Leave a Reply

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