Find the node whose sum with X has maximum set bits | C ++ implementation of the approach ; Function to perform dfs to find the maximum set bits value ; If current set bits value is greater than the current maximum ; If count is equal to the maximum then choose the node with minimum value ; Driver code ; Weights of the node ; Edges of the tree
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maximum = INT_MIN , x , ans = INT_MAX ; vector < int > graph [ 100 ] ; vector < int > weight ( 100 ) ; void dfs ( int node , int parent ) { int a = __builtin_popcount ( weight [ node ] + x ) ; if ( maximum < a ) { maximum = a ; ans = node ; } else if ( maximum == a ) ans = min ( ans , node ) ; for ( int to : graph [ node ] ) { if ( to == parent ) continue ; dfs ( to , node ) ; } } int main ( ) { x = 15 ; weight [ 1 ] = 5 ; weight [ 2 ] = 10 ; weight [ 3 ] = 11 ; weight [ 4 ] = 8 ; weight [ 5 ] = 6 ; graph [ 1 ] . push_back ( 2 ) ; graph [ 2 ] . push_back ( 3 ) ; graph [ 2 ] . push_back ( 4 ) ; graph [ 1 ] . push_back ( 5 ) ; dfs ( 1 , 1 ) ; cout << ans ; return 0 ; }