Find the smallest positive number missing from an unsorted array | Set 1 | C ++ program to find the smallest positive missing number ; Utility to swap to integers ; 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 because indexes start from 0 ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void swap ( int * a , int * b ) { int temp ; temp = * a ; * a = * b ; * b = temp ; } int segregate ( int arr [ ] , int size ) { int j = 0 , i ; for ( i = 0 ; i < size ; i ++ ) { if ( arr [ i ] <= 0 ) { swap ( & arr [ i ] , & arr [ j ] ) ; j ++ ; } } return j ; } int findMissingPositive ( int arr [ ] , int size ) { int i ; for ( i = 0 ; i < size ; i ++ ) { if ( abs ( arr [ i ] ) - 1 < size && arr [ abs ( arr [ i ] ) - 1 ] > 0 ) arr [ abs ( arr [ i ] ) - 1 ] = - arr [ abs ( arr [ i ] ) - 1 ] ; } for ( i = 0 ; i < size ; i ++ ) if ( arr [ i ] > 0 ) return i + 1 ; return size + 1 ; } int findMissing ( int arr [ ] , int size ) { int shift = segregate ( arr , size ) ; return findMissingPositive ( arr + shift , size - shift ) ; } int main ( ) { int arr [ ] = { 0 , 10 , 2 , -10 , -20 } ; int arr_size = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int missing = findMissing ( arr , arr_size ) ; cout << " The ▁ smallest ▁ positive ▁ missing ▁ number ▁ is ▁ " << missing ; return 0 ; }