Choose an integer K such that maximum of the xor values of K with all Array elements is minimized | C ++ implementation to find Minimum possible value of the maximum xor in an array by choosing some integer ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int calculate ( vector < int > & section , int pos ) { if ( pos < 0 ) return 0 ; vector < int > on_section , off_section ; for ( auto el : section ) { if ( ( ( el >> pos ) & 1 ) == 0 ) off_section . push_back ( el ) ; else on_section . push_back ( el ) ; } if ( off_section . size ( ) == 0 ) return calculate ( on_section , pos - 1 ) ; if ( on_section . size ( ) == 0 ) return calculate ( off_section , pos - 1 ) ; return min ( calculate ( off_section , pos - 1 ) , calculate ( on_section , pos - 1 ) ) + ( 1 << pos ) ; } int minXorValue ( int a [ ] , int n ) { vector < int > section ; for ( int i = 0 ; i < n ; i ++ ) section . push_back ( a [ i ] ) ; return calculate ( section , 30 ) ; } int main ( ) { int N = 4 ; int A [ N ] = { 3 , 2 , 5 , 6 } ; cout << minXorValue ( A , N ) ; return 0 ; }