Minimum number of elements that should be removed to make the array good | C ++ implementation of the approach ; Function to return the minimum number of elements that must be removed to make the given array good ; Count frequency of each element ; For each element check if there exists another element that makes a valid pair ; If does not exist then increment answer ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int minimumRemoval ( int n , int a [ ] ) { map < int , int > c ; for ( int i = 0 ; i < n ; i ++ ) c [ a [ i ] ] ++ ; int ans = 0 ; for ( int i = 0 ; i < n ; i ++ ) { bool ok = false ; for ( int j = 0 ; j < 31 ; j ++ ) { int x = ( 1 << j ) - a [ i ] ; if ( c . count ( x ) && ( c [ x ] > 1 || ( c [ x ] == 1 && x != a [ i ] ) ) ) { ok = true ; break ; } } if ( ! ok ) ans ++ ; } return ans ; } int main ( ) { int a [ ] = { 4 , 7 , 1 , 5 , 4 , 9 } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; cout << minimumRemoval ( n , a ) ; return 0 ; }