Java Program to Find the Smallest Positive Number Missing from an Unsorted Array

«
»

This is the Java Program to Find the Smallest Positive Integer Missing in an Unsorted Integer Array.

Problem Description

Given an array of integers, find out the smallest positive integer missing from the array.

advertisement

Example:
Array = [-1, -3, 3, 2, 8 ,6]

Output: 1.

Problem Solution

First sort the array. Then initialize a variable to 1 and using a loop scan through the array. Check the value of the variable if it matches the current array element, increment it if that is the case. The value of the variable after the loop is the smallest positive missing integer.

Program/Source Code
Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

Here is the source code of the Java Program to Find the Smallest Positive Integer Missing in an Unsorted Integer Array. The program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The program output is also shown below.

  1.  
  2. //Java Program to Find the Smallest Positive Integer Missing in
  3. //an Unsorted Integer Array
  4.  
  5. import java.io.BufferedReader;
  6. import java.io.InputStreamReader;
  7.  
  8. public class SmallestPositiveInteger {
  9.     // Function to find the smallest positive missing integer
  10.     static int findSmallestPositiveMissingInteger(int[] array){
  11.         Arrays.sort(array);
  12.         int j,i = 1;
  13.         for(j = 0; j<array.length; j++){
  14.            if(array[j] == i){
  15.               i++;
  16.            }
  17.         } 
  18.         return i;
  19.     }
  20.     // Function to read input and display the output
  21.     public static void main(String[] args) {
  22.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  23.         int size;
  24.         System.out.println("Enter the size of the array");
  25.         try {
  26.             size = Integer.parseInt(br.readLine());
  27.         } catch (Exception e) {
  28.             System.out.println("Invalid Input");
  29.             return;
  30.         }
  31.         int[] array = new int[size];
  32.         System.out.println("Enter array elements");
  33.         int i;
  34.         for (i = 0; i < array.length; i++) {
  35.             try {
  36.                 array[i] = Integer.parseInt(br.readLine());
  37.             } catch (Exception e) {
  38.                 System.out.println("An error occurred");
  39.                 return;
  40.             }
  41.         }
  42.         int missing = findSmallestPositiveMissingInteger(array);
  43.         System.out.println("The smallest positive missing integer is " + missing);
  44.     }
  45. }
Program Explanation

1. In function findSmallestPositiveMissingInteger, firstly the array is sorted.
2. Then, the loop for(j = 0; j<array.length; j++) traverses the array to find the smallest positive missing integer.
3. Finally, the smallest positive missing integer i is returned.

Take Java Programming Practice Tests - Chapterwise!
Start the Test Now: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
advertisement

Time Complexity: O(n*(log(n)) ) where n is the number of elements in the array.

Runtime Test Cases
 
Case 1 (Simple Test Case):
 
Enter the size of the array
6
Enter array elements
-1
-3
3
2
8
6
The smallest positive missing integer is 1
 
Case 2 (Simple Test Case - another example):
 
Enter the size of the array
5
Enter array elements
-1
-2
-3
-4
-5
The smallest positive missing integer is 1

Sanfoundry Global Education & Learning Series – Java Programs.

advertisement

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.