Count of paths in given Binary Tree with odd bitwise AND for Q queries | Function to count number of paths in binary tree such that bitwise AND of all nodes is Odd ; vector 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 ; vector to store queries
function compute ( query ) { var v = Array ( 100001 ) . fill ( 0 ) ; var dp = Array ( 100001 ) . fill ( 0 ) ; v [ 1 ] = 1 , v [ 2 ] = 0 ; dp [ 1 ] = 0 , dp [ 2 ] = 0 ; for ( var i = 3 ; i < 100001 ; i ++ ) { if ( i % 2 != 0 ) { if ( parseInt ( i / 2 ) % 2 == 0 ) { v [ i ] = 1 ; dp [ i ] = dp [ i - 1 ] ; } else { v [ i ] = v [ parseInt ( i / 2 ) ] + 1 ; dp [ i ] = dp [ i - 1 ] + v [ i ] - 1 ; } } else { v [ i ] = 0 ; dp [ i ] = dp [ i - 1 ] ; } } query . forEach ( x => { document . write ( dp [ x ] + " " ) ; } ) ; } var query = [ 5 , 2 ] ; compute ( query ) ;