Smallest Positive missing number in Java

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:

  1. Create a new HashMap to store positive integers in the array.
  2. Loop through the array, and for each positive integer in the array, insert it as a key in the HashMap.
  3. 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.
  4. 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 GeeksforGeeksCodesagar only provides a solution for it. This solution is only for Educational and learning purposes.

Leave a Comment