Find the smallest positive missing number in the given array.
Example: [0, -10, 1, 3, -20], Ans = 2
Constrains:
1<=N<=10^6
-10^6<=Ai<=10^6
This question has been asked in companies like amazon, samsung, snapdeal etc.
To solve this question click here:(https://practice.geeksforgeeks.org/problems/smallest-positive-missing-number-1587115621/1)
Approach 1:
We can solve the problem naively by looping over all the positive integers and checking if each of them is present in the array or not. Whenever a number is not found in the array, we return it and break the algorithm. Time compexity:O(n^2)
Approach 2:
We can solve this problem in linear time by using hashing. We loop over all the positive numbers, and check if it is present in the array or not by using a lookup table or hash map in O(1) time. The first element not found in the array will be the answer.
JAVA CODE:
import java.util.*;
import java.util.HashSet;
public class Smallest_pos_missing_no {
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
System.out.println("Enter a number:");
int n=sc.nextInt();
int[] arr=new int[n];
System.out.println("Enter the elements of the array:");
for(int i=0;i<n;i++)
{
arr[i]=sc.nextInt();
}
int res= smallest_pos(arr,n);
System.out.println(res);
}
public static int smallest_pos(int arr[],int n)
{
HashSet<Integer> hash=new HashSet<Integer>();
for(int i=0;i<n;i++)
{
hash.add(arr[i]);
}
for(int i=1;i<=n+1;i++)
{
if(!hash.contains(i))
{
return i;
}
}
return -1;
}
}
Top comments (2)
In JS, the solution would be filtering negative numbers and comparing to the index:
Obviously, if the positive numbers don't start at zero, we need to find out the starting number and add that as difference.
Since filter already creates a new array, there's no need to destructure it.
The only "real world application" I can think of is usually job interviews.