Connect a graph by M edges such that the graph does not contain any cycle and Bitwise AND of connected vertices is maximum | C ++ program for the above approach ; Function to find the maximum Bitwise AND of connected components possible by connecting a graph using M edges ; Stores total number of ways to connect the graph ; Stores the maximum Bitwise AND ; Iterate over the range [ 0 , 2 ^ n ] ; Store the Bitwise AND of the connected vertices ; Store the count of the connected vertices ; Check for all the bits ; If i - th bit is set ; If the first vertex is added ; Set andans equal to arr [ i ] ; Calculate Bitwise AND of arr [ i ] with andans ; Increase the count of connected vertices ; If number of connected vertices is ( m + 1 ) , no cycle is formed ; Find the maximum Bitwise AND value possible ; Return the maximum Bitwise AND possible ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maximumAND ( int arr [ ] , int n , int m ) { int tot = 1 << n ; int mx = 0 ; for ( int bm = 0 ; bm < tot ; bm ++ ) { int andans = 0 ; int count = 0 ; for ( int i = 0 ; i < n ; ++ i ) { if ( ( bm >> i ) & 1 ) { if ( count == 0 ) { andans = arr [ i ] ; } else { andans = andans & arr [ i ] ; } count ++ ; } } if ( count == ( m + 1 ) ) { mx = max ( mx , andans ) ; } } return mx ; } int main ( ) { int arr [ ] = { 1 , 2 , 3 , 4 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int M = 2 ; cout << maximumAND ( arr , N , M ) ; return 0 ; }