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 ; 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 ; Driver code ; vector to store queries
#include <bits/stdc++.h> NEW_LINE using namespace std ; void compute ( vector < int > query ) { vector < int > v ( 100001 ) , dp ( 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 ] ; } } for ( auto x : query ) cout << dp [ x ] << endl ; } int main ( ) { vector < int > query = { 5 , 2 } ; compute ( query ) ; return 0 ; }