Queries to find the maximum Xor value between X and the nodes of a given level of a perfect binary tree | Python3 implementation of the approach ; Function to solve queries of the maximum xor value between the nodes in a given level L of a perfect binary tree and a given value X ; Initialize result ; Initialize array to store bits ; Initialize a copy of X and size of array ; Storing the bits of X in the array a [ ] ; Filling the array b [ ] ; Initializing variable which gives maximum xor ; Getting the maximum xor value ; Return the result ; Driver code ; Perform queries
MAXN = 60 NEW_LINE def solveQuery ( L , X ) : NEW_LINE INDENT res = 0 NEW_LINE a = [ 0 for i in range ( MAXN ) ] NEW_LINE b = [ 0 for i in range ( MAXN ) ] NEW_LINE ref = X NEW_LINE size_a = 0 NEW_LINE while ( ref > 0 ) : NEW_LINE INDENT a [ size_a ] = ref % 2 NEW_LINE ref //= 2 NEW_LINE size_a += 1 NEW_LINE DEDENT for i in range ( min ( size_a , L ) ) : NEW_LINE INDENT if ( a [ i ] == 1 ) : NEW_LINE INDENT b [ i ] = 0 NEW_LINE DEDENT else : NEW_LINE INDENT b [ i ] = 1 NEW_LINE DEDENT DEDENT for i in range ( min ( size_a , L ) , L ) : NEW_LINE INDENT b [ i ] = 1 NEW_LINE DEDENT b [ L - 1 ] = 1 NEW_LINE temp = 0 NEW_LINE p = 1 NEW_LINE for i in range ( L ) : NEW_LINE INDENT temp += b [ i ] * p NEW_LINE p *= 2 NEW_LINE DEDENT res = temp ^ X NEW_LINE return res NEW_LINE DEDENT queries = [ [ 2 , 5 ] , [ 3 , 15 ] ] NEW_LINE q = len ( queries ) NEW_LINE for i in range ( q ) : NEW_LINE INDENT print ( solveQuery ( queries [ i ] [ 0 ] , queries [ i ] [ 1 ] ) ) NEW_LINE DEDENT