Count of paths in given Binary Tree with odd bitwise AND for Q queries | C # implementation to count paths in Binary Tree with odd bitwise AND ; Function to count number of paths in binary tree such that bitwise AND of all nodes is Odd ; dp to store the count of bitwise odd paths till that vertex ; Precomputing for each value ; Check for odd value ; Number of odd elements will be + 1 till the parent node ; For even case ; Since node is even Number of odd elements will be 0 ; Even value node will not contribute in answer hence dp [ i ] = previous answer ; Printing the answer for each query ; Driver code ; To store queries
using System ; class GFG { static void compute ( int [ ] query ) { int [ ] v = new int [ 100001 ] ; int [ ] dp = new int [ 100001 ] ; v [ 1 ] = 1 ; v [ 2 ] = 0 ; dp [ 1 ] = 0 ; dp [ 2 ] = 0 ; for ( int i = 3 ; i < 100001 ; i ++ ) { if ( i % 2 != 0 ) { if ( ( i / 2 ) % 2 == 0 ) { v [ i ] = 1 ; dp [ i ] = dp [ i - 1 ] ; } else { v [ i ] = v [ i / 2 ] + 1 ; dp [ i ] = dp [ i - 1 ] + v [ i ] - 1 ; } } else { v [ i ] = 0 ; dp [ i ] = dp [ i - 1 ] ; } } foreach ( int x in query ) Console . Write ( dp [ x ] + " STRNEWLINE " ) ; } public static void Main ( String [ ] args ) { int [ ] query = { 5 , 2 } ; compute ( query ) ; } }