Hi Guys, Welcome to Proto Coders Point. Here is the solution for a problem statement “Find the smallest positive number that does not appear in array”. – JAVA PROGRAM

Number system x
Number system

You car given a Array (Sorted/UnSorted), You need to search the missing small number in the array.

Example

Array { 1, 4, 5, 7, 6 }

Here the missing smallest number starting from 1 to N is checked, so as you can see missing number in above array is 2. After 1 we directly have 4, 5, 7, 6. Therefore 2 is smallest number & is missing .

Example 2

Array { 6, 5, 1, 2, 3, 7 } output: 4.


Source Code JAVA Program – To Find the positive smallest number missing in Array

import java.util.*;
import java.util.Arrays;

class HelloWorld {
    public static void main(String[] args) {
       
        int arr[] = {6,5,1,2,3,7};

        int result = findMissSmall(arr);

       System.out.println(""+result );
    }

    static public int findMissSmall(int[] A) {
        
        int len = A.length;
        int min=1;
        Arrays.sort(A);
   
        if(A[len-1]>0)
        for(int i=0; i<len; i++){
            if(A[i]>0){
                if(A[i]==min) min=min+1;
                if(A[i]>min) break;
            }
        }
        return min;
    }
}

In code, we have manully declared an array & then we are passing the array to findMissSmall() function that iterate through the arrray and return us the smallest missing number in the list.

Let’s understand how findMissSmall() function works

  1. get length of array.
  2. set min = 1.
  3. sort the array.
  4. Perform for-loop to get smallest missing num.

Let’s take the array for tracing with above program

arr = { 6, 2, 1, 5 }

after sorting arr = { 1, 2, 5, 6 }

In for loop

Iteration 1

i = 0, len = 4, min = 1, arr = { 1, 2, 5, 6 }

if( A[i] == min ) // 1 = 1 true, so increment min
min = min + 1; // min = 2


Iteration 2

i = 1, len = 4, min = 2, arr = { 1, 2, 5, 6 }

if( A[i] == min ) // 2 = 2 true, so increment min
min = min + 1; // min = 3


Iteration 3

i = 2, len = 4, min = 3, arr = { 1, 2, 5, 6 }

if( A[i] == min ) // 5 = 3 false, so don’t increment min
min = min + 1;

if( A[i] > min)
break; // 5 > 3 true,

In iteration 3, A[i] is not equal to min i.e 5 != 3, so dont increment min, then check if A[i] > min i.e 5 > 3 so break the for loop and come out.


Finally we have found smallest missing number in Array, return min = 3.

Note: Trace above program by your own Array, it will improve your programming logic & skill & code thinking.