Find triplets in an array whose AND is maximum | CPP program to find triplet with maximum bitwise AND . ; Flag Array initially set to true for all numbers ; 2D array for bit representation of all the numbers . Initially all bits are set to 0. ; Finding bit representation of every number and storing it in bits array . ; Checking last bit of the number ; Dividing number by 2. ; maximum And number initially 0. ; Traversing the 2d binary representation . 0 th index represents 32 th bits while 32 th index represents 0 th bit . ; If cnt greater than 3 then ( 32 - i ) th bits of the number will be set . ; Setting flags of the numbers whose ith bit is not set . ; Counting the numbers whose flag are true . ; Driver code
#include " cmath " NEW_LINE #include " cstring " NEW_LINE #include " iostream " NEW_LINE using namespace std ; int maxTriplet ( int a [ ] , int n ) { bool f [ n ] ; memset ( f , true , sizeof ( f ) ) ; int bits [ n ] [ 33 ] ; memset ( bits , 0 , sizeof ( bits ) ) ; for ( int i = 0 ; i < n ; ++ i ) { int num = a [ i ] ; int j = 32 ; while ( num ) { if ( num & 1 ) { bits [ i ] [ j ] = 1 ; } j -- ; num >>= 1 ; } } long long ans = 0 ; for ( long long i = 0 ; i <= 32 ; ++ i ) { int cnt = 0 ; for ( int j = 0 ; j < n ; ++ j ) { if ( bits [ j ] [ i ] and f [ j ] ) { cnt ++ ; } } if ( cnt >= 3 ) { ans += pow ( 2LL , 32 - i ) ; for ( int j = 0 ; j < n ; ++ j ) { if ( ! bits [ j ] [ i ] ) { f [ j ] = false ; } } } } int cnt = 0 ; for ( int i = 0 ; i < n ; ++ i ) { if ( f [ i ] ) { cnt ++ ; } } long long NumberOfTriplets = ( cnt * ( cnt - 1 ) * ( cnt - 2 ) ) / 6 ; cout << NumberOfTriplets << " ▁ " << ans ; } int main ( int argc , char const * argv [ ] ) { int a [ ] = { 4 , 11 , 10 , 15 , 26 } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; maxTriplet ( a , n ) ; return 0 ; }