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 In Java , helper is automatically 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
def missing4 ( arr ) : NEW_LINE INDENT helper = [ 0 ] * 4 NEW_LINE for i in range ( 0 , len ( arr ) ) : NEW_LINE INDENT temp = abs ( arr [ i ] ) NEW_LINE if ( temp <= len ( arr ) ) : NEW_LINE INDENT arr [ temp - 1 ] = arr [ temp - 1 ] * ( - 1 ) NEW_LINE DEDENT elif ( temp > len ( arr ) ) : NEW_LINE INDENT if ( temp % len ( arr ) ) : NEW_LINE INDENT helper [ temp % len ( arr ) - 1 ] = - 1 NEW_LINE DEDENT else : NEW_LINE INDENT helper [ ( temp % len ( arr ) ) + len ( arr ) - 1 ] = - 1 NEW_LINE DEDENT DEDENT DEDENT for i in range ( 0 , len ( arr ) ) : NEW_LINE INDENT if ( arr [ i ] > 0 ) : NEW_LINE INDENT print ( ( i + 1 ) , end = " ▁ " ) NEW_LINE DEDENT DEDENT for i in range ( 0 , len ( helper ) ) : NEW_LINE INDENT if ( helper [ i ] >= 0 ) : NEW_LINE INDENT print ( ( len ( arr ) + i + 1 ) , end = " ▁ " ) NEW_LINE DEDENT DEDENT DEDENT arr = [ 1 , 7 , 3 , 12 , 5 , 10 , 8 , 4 , 9 ] NEW_LINE missing4 ( arr ) NEW_LINE