Find the smallest positive number missing from an unsorted array | Set 1 | Java program to find the smallest positive missing number ; Utility function that puts all non - positive ( 0 and negative ) numbers on left side of arr [ ] and return count of such numbers ; increment count of non - positive integers ; Find the smallest positive missing number in an array that contains all positive integers ; Mark arr [ i ] as visited by making arr [ arr [ i ] - 1 ] negative . Note that 1 is subtracted because index start from 0 and positive numbers start from 1 ; Return the first index value at which is positive ; 1 is added becuase indexes ; Find the smallest positive missing number in an array that contains both positive and negative integers ; First separate positive and negative numbers ; Shift the array and call findMissingPositive for positive part ; Driver code
import java . util . * ; class Main { static int segregate ( int arr [ ] , int size ) { int j = 0 , i ; for ( i = 0 ; i < size ; i ++ ) { if ( arr [ i ] <= 0 ) { int temp ; temp = arr [ i ] ; arr [ i ] = arr [ j ] ; arr [ j ] = temp ; j ++ ; } } return j ; } static int findMissingPositive ( int arr [ ] , int size ) { int i ; for ( i = 0 ; i < size ; i ++ ) { int x = Math . abs ( arr [ i ] ) ; if ( x - 1 < size && arr [ x - 1 ] > 0 ) arr [ x - 1 ] = - arr [ x - 1 ] ; } for ( i = 0 ; i < size ; i ++ ) if ( arr [ i ] > 0 ) return i + 1 ; return size + 1 ; } static int findMissing ( int arr [ ] , int size ) { int shift = segregate ( arr , size ) ; int arr2 [ ] = new int [ size - shift ] ; int j = 0 ; for ( int i = shift ; i < size ; i ++ ) { arr2 [ j ] = arr [ i ] ; j ++ ; } return findMissingPositive ( arr2 , j ) ; } public static void main ( String [ ] args ) { int arr [ ] = { 0 , 10 , 2 , - 10 , - 20 } ; int arr_size = arr . length ; int missing = findMissing ( arr , arr_size ) ; System . out . println ( " The ▁ smallest ▁ positive ▁ missing ▁ number ▁ is ▁ " + missing ) ; } }