You are given an array arr[] of N integers including 0. The task is to find the smallest positive number missing from the array.
Example 1:
Input: N = 5 arr[] = {1,2,3,4,5} Output: 6
Here’s an algorithm for the missingNumber method:
- Create a new HashMap to store positive integers in the array.
- Loop through the array, and for each positive integer in the array, insert it as a key in the HashMap.
- Loop through integers from 1 to size:
a. Check if the current integer is present as a key in the HashMap. If it is not, return the integer. - If all integers from 1 to size are present in the HashMap, return size+1 as the smallest missing positive integer.
.
Smallest Positive missing number in Java
class Solution { //Function to find the smallest positive number missing from the array. static int missingNumber(int arr[], int size) { // Your code here HashMap<Integer,Integer> hm=new HashMap<Integer,Integer>(); for(int i=0;i<size;i++){ if(arr[i]>0){ hm.put(arr[i],1); } } for(int i=1;i<=size;i++){ if(!hm.containsKey(i)) return i; } return size+1; } }
This Java code defines a class named Solution
that contains a static method named missingNumber
. This method takes two arguments: an array of integers arr
and an integer size
representing the size of the array. The method returns an integer representing the smallest positive number missing from the array.
The implementation of the missingNumber
method uses a HashMap
to keep track of the positive integers in the array. In the first loop, each positive integer in the array is inserted as a key into the HashMap
. The value associated with the key is not important, as we only care about whether or not the key exists in the HashMap
.
In the second loop, we check for the smallest positive integer missing from the array. We iterate over integers from 1 to size
and for each integer i
, we check if it is present as a key in the HashMap
. If it is not, then i
is the smallest positive integer missing from the array, and we return it.
If all integers from 1 to size
are present in the HashMap
, then the smallest missing positive integer must be size + 1
, which we return as the answer.
Disclaimer: This problem(Smallest Positive Missing Number) is originally created by GeeksforGeeks. Codesagar only provides a solution for it. This solution is only for Educational and learning purposes.