text: Find four missing numbers in an array containing elements from 1 to N | CPP program to find missing 4 elements in an array of size N where elements are in range from 1 to N + 4. ; 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
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; void missing4 ( int arr [ ] , int n ) { int helper [ 4 ] ; for ( int i = 0 ; i < n ; i ++ ) { int temp = abs ( arr [ i ] ) ; if ( temp <= n ) 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 ( int i = 0 ; i < n ; i ++ ) if ( arr [ i ] > 0 ) cout << ( i + 1 ) << " ▁ " ; for ( int i = 0 ; i < 4 ; i ++ ) if ( helper [ i ] >= 0 ) cout << ( n + i + 1 ) << " ▁ " ; return ; } int main ( ) { int arr [ ] = { 1 , 7 , 3 , 12 , 5 , 10 , 8 , 4 , 9 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; missing4 ( arr , n ) ; return 0 ; }