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[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 missing smallest positive number from the array. Some of them are:
METHOD 1: Brute-Force Solution to 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 Based to 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:
- Program to sort if array is sorted.
- Program to print Alternate Elements of an Array.
- Program to swap kth element from beginning to kth element from end in an Array.
- Program to print all possible subarrays of the given array.
- Program to print kth smallest and kth largest element of an Array.
- Program to find equilibrium index of an Array.
- Program to find majority element of an Array.
- Program to find mean of the Array.
- Program to sort an Array of 0s and 1s.
- Program to convert lower-case alphabet to upper-case alphabet and vice-versa.
- Program to count total number of words in a string.
- Program to find smallest and largest word of the String.
- Program to find Most Frequent Character of the String.
- Program to Remove all the blank spaces from the String.
- Program to check if String is isogram or not.
- Program to Reverse Each word of the String.
- Program to Print All the Substring of the Given String.
- Program to find longest palindromic Substring.
- Program to check Anagram Strings.
- Program to check whether two Strings are Rotation of each other or not.
