Choose an integer K such that maximum of the xor values of K with all Array elements is minimized | Function to calculate Minimum possible value of the Maximum XOR in an array ; base case ; Divide elements into two sections ; Traverse all elements of current section and divide in two groups ; Check if one of the sections is empty ; explore both the possibilities using recursion ; Function to calculate minimum XOR value ; Start recursion from the most significant pos position ; Driver code
def calculate ( section , pos ) : NEW_LINE INDENT if ( pos < 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT on_section = [ ] NEW_LINE off_section = [ ] NEW_LINE for el in section : NEW_LINE INDENT if ( ( ( el >> pos ) & 1 ) == 0 ) : NEW_LINE INDENT off_section . append ( el ) NEW_LINE DEDENT else : NEW_LINE INDENT on_section . append ( el ) NEW_LINE DEDENT DEDENT if ( len ( off_section ) == 0 ) : NEW_LINE INDENT return calculate ( on_section , pos - 1 ) NEW_LINE DEDENT if ( len ( on_section ) == 0 ) : NEW_LINE INDENT return calculate ( off_section , pos - 1 ) NEW_LINE DEDENT return min ( calculate ( off_section , pos - 1 ) , calculate ( on_section , pos - 1 ) ) + ( 1 << pos ) NEW_LINE DEDENT def minXorValue ( a , n ) : NEW_LINE INDENT section = [ ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT section . append ( a [ i ] ) ; NEW_LINE DEDENT return calculate ( section , 30 ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 4 NEW_LINE A = [ 3 , 2 , 5 , 6 ] NEW_LINE print ( minXorValue ( A , N ) ) NEW_LINE DEDENT