Smallest element with K set bits such that sum of Bitwise AND of each array element with K is maximum | Java program for the above approach ; 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
import java . io . * ; import java . lang . * ; import java . util . * ; class GFG { static void maximizeSum ( int arr [ ] , int n , int k ) { int cnt [ ] = new int [ 30 ] ; int X = 0 ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < 30 ; j ++ ) { if ( ( arr [ i ] & ( 1 << j ) ) != 0 ) cnt [ j ] ++ ; } } ArrayList < int [ ] > v = new ArrayList < > ( ) ; for ( int i = 0 ; i < 30 ; i ++ ) { int gain = cnt [ i ] * ( 1 << i ) ; v . add ( new int [ ] { i , gain } ) ; } Collections . sort ( v , ( a , b ) -> { if ( a [ 1 ] != b [ 1 ] ) return b [ 1 ] - a [ 1 ] ; return a [ 0 ] - b [ 0 ] ; } ) ; for ( int i = 0 ; i < k ; i ++ ) { X |= ( 1 << v . get ( i ) [ 0 ] ) ; } System . out . println ( X ) ; } public static void main ( String [ ] args ) { int arr [ ] = { 3 , 4 , 5 , 1 } ; int K = 1 ; int N = arr . length ; maximizeSum ( arr , N , K ) ; } }