Smallest positive missing number

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; } }