Smallest element with K set bits such that sum of Bitwise AND of each array element with K is maximum | C ++ program for the above approach ; Comparator function to sort the vector of pairs ; Function to find the value of X such that Bitwise AND of all array elements with X is maximum ; Stores the count of set bit at each position ; Stores the resultant value of X ; Calculate the count of set bits at each position ; If the jth bit is set ; Stores the contribution of each set bit ; Store all bit and amount of contribution ; Find the total contribution ; Sort V [ ] in decreasing order of second parameter ; Choose exactly K set bits ; Print the answer ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool comp ( pair < int , int > & a , pair < int , int > & b ) { if ( a . second != b . second ) return a . second > b . second ; return a . first < b . first ; } int maximizeSum ( int arr [ ] , int n , int k ) { vector < int > cnt ( 30 , 0 ) ; int X = 0 ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < 30 ; j ++ ) { if ( arr [ i ] & ( 1 << j ) ) cnt [ j ] ++ ; } } vector < pair < int , int > > v ; for ( int i = 0 ; i < 30 ; i ++ ) { int gain = cnt [ i ] * ( 1 << i ) ; v . push_back ( { i , gain } ) ; } sort ( v . begin ( ) , v . end ( ) , comp ) ; for ( int i = 0 ; i < k ; i ++ ) { X |= ( 1 << v [ i ] . first ) ; } cout << X ; } int main ( ) { int arr [ ] = { 3 , 4 , 5 , 1 } ; int K = 1 ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; maximizeSum ( arr , N , K ) ; return 0 ; }