Find the node whose sum with X has maximum set bits | C # implementation of the approach ; number of set bits ; Function to perform dfs to find the maximum 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
using System ; using System . Collections . Generic ; class GFG { static int maximum = int . MinValue , x , ans = int . MaxValue ; static List < List < int > > graph = new List < List < int > > ( ) ; static List < int > weight = new List < int > ( ) ; static int __builtin_popcount ( int x ) { int c = 0 ; for ( int i = 0 ; i < 60 ; i ++ ) if ( ( ( x >> i ) & 1 ) != 0 ) c ++ ; return c ; } static 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 = Math . Min ( ans , node ) ; for ( int i = 0 ; i < graph [ node ] . Count ; i ++ ) { if ( graph [ node ] [ i ] == parent ) continue ; dfs ( graph [ node ] [ i ] , node ) ; } } public static void Main ( ) { x = 15 ; weight . Add ( 0 ) ; weight . Add ( 5 ) ; weight . Add ( 10 ) ; weight . Add ( 11 ) ; ; weight . Add ( 8 ) ; weight . Add ( 6 ) ; for ( int i = 0 ; i < 100 ; i ++ ) graph . Add ( new List < int > ( ) ) ; graph [ 1 ] . Add ( 2 ) ; graph [ 2 ] . Add ( 3 ) ; graph [ 2 ] . Add ( 4 ) ; graph [ 1 ] . Add ( 5 ) ; dfs ( 1 , 1 ) ; Console . Write ( ans ) ; } }