Given an array A consisting of N non-negative integers, the task is to choose an integer K such that the maximum of the xor values of K with all array elements is minimized. In other words find the minimum possible value of Z, where Z = max(A[i] xor K), 0 <= i <= n-1, for some value of K.Â
Examples:Â
Â
Input: A = [1, 2, 3]Â
Output: 2Â
Explanation:Â
On choosing K = 3, max(A[i] xor 3) = 2, and this is the minimum possible value.
Input: A = [3, 2, 5, 6]Â
Output: 5Â
Â
Â
Approach: To solve the problem mentioned above we will use recursion. We will start from the most significant bit in the recursive function.Â
Â
- In the recursive step, split the element into two sections – one having the current bit on and the other with current bit off. If any of the sections doesn’t have a single element, then this particular bit for K can be chosen such that the final xor value has 0 at this bit position (since our aim is to minimise this value) and then proceed to the next bit in the next recursive step.Â
 - If both the sections have some elements, then explore both the possibilities by placing 0 and 1 at this bit position and calculating the answer using the corresponding section in next recursive call.Â
Let answer_on be the value if 1 is placed and answer_off be the value if 0 is placed at this position (pos). Since both sections are non empty whichever bit we choose for K, 2pos will be added to the final value.Â
For each recursive step:Â
Â
answer = min(answer_on, answer_off) + 2posÂ
Â
Â
Below is the implementation of the above approach:Â
Â
C++
// C++ implementation to find Minimum// possible value of the maximum xor// in an array by choosing some integerÂ
#include <bits/stdc++.h>using namespace std;Â
// Function to calculate Minimum possible// value of the Maximum XOR in an arrayint calculate(vector<int>& section, int pos){    // base case    if (pos < 0)        return 0;Â
    // Divide elements into two sections    vector<int> on_section, off_section;Â
    // Traverse all elements of current    // section and divide in two groups    for (auto el : section) {        if (((el >> pos) & 1) == 0)            off_section.push_back(el);Â
        else            on_section.push_back(el);    }Â
    // Check if one of the sections is empty    if (off_section.size() == 0)        return calculate(on_section, pos - 1);Â
    if (on_section.size() == 0)        return calculate(off_section, pos - 1);Â
    // explore both the possibilities using recursion    return min(calculate(off_section, pos - 1),               calculate(on_section, pos - 1))           + (1 << pos);}Â
// Function to calculate minimum XOR valueint minXorValue(int a[], int n){Â Â Â Â vector<int> section;Â Â Â Â for (int i = 0; i < n; i++)Â Â Â Â Â Â Â Â section.push_back(a[i]);Â
    // Start recursion from the    // most significant pos position    return calculate(section, 30);}Â
// Driver codeint main(){Â Â Â Â int N = 4;Â
    int A[N] = { 3, 2, 5, 6 };Â
    cout << minXorValue(A, N);Â
    return 0;} |
Java
// Java implementation to find Minimum// possible value of the maximum xor// in an array by choosing some integerimport java.util.*;Â
class GFG{Â
// Function to calculate Minimum possible// value of the Maximum XOR in an arraystatic int calculate(Vector<Integer> section, int pos){Â
    // Base case    if (pos < 0)        return 0;Â
    // Divide elements into two sections    Vector<Integer> on_section = new Vector<Integer>(),                    off_section = new Vector<Integer>();Â
    // Traverse all elements of current    // section and divide in two groups    for(int el : section)     {       if (((el >> pos) & 1) == 0)           off_section.add(el);       else           on_section.add(el);    }Â
    // Check if one of the sections is empty    if (off_section.size() == 0)        return calculate(on_section, pos - 1);Â
    if (on_section.size() == 0)        return calculate(off_section, pos - 1);Â
    // Explore both the possibilities using recursion    return Math.min(calculate(off_section, pos - 1),                    calculate(on_section, pos - 1)) +                             (1 << pos);}Â
// Function to calculate minimum XOR valuestatic int minXorValue(int a[], int n){Â Â Â Â Vector<Integer> section = new Vector<Integer>();Â
    for(int i = 0; i < n; i++)       section.add(a[i]);Â
    // Start recursion from the    // most significant pos position    return calculate(section, 30);}Â
// Driver codepublic static void main(String[] args){Â Â Â Â int N = 4;Â Â Â Â int A[] = { 3, 2, 5, 6 };Â
    System.out.print(minXorValue(A, N));}}Â
// This code is contributed by Princi Singh |
Python3
# Python3 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Â
def calculate(section, pos):Â
    # base case    if (pos < 0):        return 0      # Divide elements into two sections    on_section = []    off_section = []      # Traverse all elements of current    # section and divide in two groups    for el in section:        if (((el >> pos) & 1) == 0):            off_section.append(el)          else:            on_section.append(el)      # Check if one of the sections is empty    if (len(off_section) == 0):        return calculate(on_section, pos - 1)      if (len(on_section) == 0):        return calculate(off_section, pos - 1)      # explore both the possibilities using recursion    return min(calculate(off_section, pos - 1),               calculate(on_section, pos - 1))+ (1 << pos)  # Function to calculate minimum XOR valuedef minXorValue(a, n):    section = []    for i in range( n):        section.append(a[i]);      # Start recursion from the    # most significant pos position    return calculate(section, 30)  # Driver codeif __name__ == "__main__":    N = 4      A = [ 3, 2, 5, 6 ]      print(minXorValue(A, N))  # This code is contributed by chitranayal   |
C#
// C# implementation to find minimum// possible value of the maximum xor// in an array by choosing some integerusing System;using System.Collections.Generic;Â
class GFG{Â
// Function to calculate minimum possible// value of the maximum XOR in an arraystatic int calculate(List<int> section, int pos){         // Base case    if (pos < 0)        return 0;Â
    // Divide elements into two sections    List<int> on_section = new List<int>(),              off_section = new List<int>();Â
    // Traverse all elements of current    // section and divide in two groups    foreach(int el in section)     {        if (((el >> pos) & 1) == 0)            off_section.Add(el);        else            on_section.Add(el);    }Â
    // Check if one of the sections is empty    if (off_section.Count == 0)        return calculate(on_section, pos - 1);Â
    if (on_section.Count == 0)        return calculate(off_section, pos - 1);Â
    // Explore both the possibilities using recursion    return Math.Min(calculate(off_section, pos - 1),                    calculate(on_section, pos - 1)) +                             (1 << pos);}Â
// Function to calculate minimum XOR valuestatic int minXorValue(int []a, int n){Â Â Â Â List<int> section = new List<int>();Â
    for(int i = 0; i < n; i++)       section.Add(a[i]);Â
    // Start recursion from the    // most significant pos position    return calculate(section, 30);}Â
// Driver codepublic static void Main(String[] args){Â Â Â Â int N = 4;Â Â Â Â int []A = { 3, 2, 5, 6 };Â
    Console.Write(minXorValue(A, N));}}Â
// This code is contributed by Princi Singh |
Javascript
<script>// Javascript 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 arrayfunction calculate(section, pos){    // base case    if (pos < 0)        return 0;Â
    // Divide elements into two sections    let on_section = [], off_section = [];Â
    // Traverse all elements of current    // section and divide in two groups    for (let el = 0; el < section.length; el++) {        if (((section[el] >> pos) & 1) == 0)            off_section.push(section[el]);Â
        else            on_section.push(section[el]);    }Â
    // Check if one of the sections is empty    if (off_section.length == 0)        return calculate(on_section, pos - 1);Â
    if (on_section.length == 0)        return calculate(off_section, pos - 1);Â
    // explore both the possibilities using recursion    return Math.min(calculate(off_section, pos - 1),               calculate(on_section, pos - 1))           + (1 << pos);}Â
// Function to calculate minimum XOR valuefunction minXorValue(a, n){Â Â Â Â let section = [];Â Â Â Â for (let i = 0; i < n; i++)Â Â Â Â Â Â Â Â section.push(a[i]);Â
    // Start recursion from the    // most significant pos position    return calculate(section, 30);}Â
// Driver code    let N = 4;Â
    let A = [ 3, 2, 5, 6 ];Â
    document.write(minXorValue(A, N));Â
</script> |
Output:Â
5
Â
Time Complexity: O(N * log(max(Ai))
Space complexity: O(NlogN)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
