Find four missing numbers in an array containing elements from 1 to N | Finds missing 4 numbers in O ( N ) time and O ( 1 ) auxiliary space . ; To keep track of 4 possible numbers greater than length of input array initialized as 0. ; Traverse the input array and mark visited elements either by marking them as negative in arr [ ] or in helper [ ] . ; If element is smaller than or equal to length , mark its presence in arr [ ] ; Mark presence in helper [ ] ; Print all those elements whose presence is not marked . ; Driver code
< ? php function missing4 ( $ arr , $ n ) { $ helper = array ( 0 , 0 , 0 , 0 ) ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) { $ temp = abs ( $ arr [ $ i ] ) ; if ( $ temp <= $ n ) $ arr [ $ temp - 1 ] = $ arr [ $ temp - 1 ] * ( -1 ) ; else if ( $ temp > $ n ) { if ( $ temp % $ n != 0 ) $ helper [ $ temp % $ n - 1 ] = -1 ; else $ helper [ ( $ temp % $ n ) + $ n - 1 ] = -1 ; } } for ( $ i = 0 ; $ i < $ n ; $ i ++ ) if ( $ arr [ $ i ] > 0 ) { $ a = $ i + 1 ; echo " $ a " , " ▁ " ; } for ( $ i = 0 ; $ i < 4 ; $ i ++ ) if ( $ helper [ $ i ] >= 0 ) { $ b = $ n + $ i + 1 ; echo " $ b " , " ▁ " ; } echo " STRNEWLINE " ; return ; } $ arr = array ( 1 , 7 , 3 , 12 , 5 , 10 , 8 , 4 , 9 ) ; $ n = sizeof ( $ arr ) ; missing4 ( $ arr , $ n ) ; ? >