Yet Another Minimax Problem

                            Solution in C :

In C++ :





#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cmath>

using namespace std;

int n,i,j,a[3005],p[3005],siz[3005];

struct edge{
	int x,y,cost;
	bool operator < (const edge& T) const{
		return cost < T.cost;
	}
};

vector <edge> b;

int find(int s){
	if(p[s] == s)
	return s;
	return p[s] = find(p[s]);
}

int main(){
	scanf("%d", &n);
	for(i = 0; i < n; i++)
	scanf("%d", &a[i]);
	for(i = 0; i < n; i++){
		p[i] = i;
		siz[i] = 1;
	}
	for(i = 0; i < n; i++){
		for(j = i + 1; j < n; j++){
			b.push_back({i ,j , a[i] ^ a[j]});
		}
	}
	sort(b.begin(), b.end());
	for(i = 0; i < b.size(); i++){
		int x = find(b[i].x);
		int y = find(b[i].y);
		if(x != y){
			p[x] = y;
			siz[y] += siz[x];
		}
		if(siz[y] == n)
		return 0 * printf("%d\n", b[i].cost);
	}
}








In Java :





import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        Arrays.sort(a);
        
        if (a[0]==a[n-1]) {
            System.out.println(0);
            return;
        }
        
        int min = 0;
        int max = 0;
        
        for (int i = 1; i < 31; i++) {
            if (a[0] >= (1<<i))
                min++;
        }
        
        for (int i = 1; i < 31; i++) {
            if (a[n-1] >= (1<<i))
                max++;
        }
        
        while (min==max&&min!=0) {
            for (int i = 0; i < n; i++) {
                a[i] -= 1<<min;
            }
            min = 0;
            max = 0;
            for (int i = 1; i < 31; i++) {
                if (a[0] >= (1<<i))
                    min++;
            }
            for (int i = 1; i < 31; i++) {
                if (a[n-1] >= (1<<i))
                    max++;
            }
        }
        
        if (max==0) {
            System.out.println(0);
            return;
        }
        
        ArrayList<Integer> l = new ArrayList<Integer>();
        ArrayList<Integer> h = new ArrayList<Integer>();
        
        for (int i = 0; i < n; i++) {
            if (a[i] < (1<<max))
                l.add(a[i]);
            else
                h.add(a[i]);
        }
        
        int result = Integer.MAX_VALUE;
        for (int i : l) {
            for (int j : h) {
                if ((i^j)<result)
                    result = i^j;
                if (result == (1<<max))
                    break;
            }
            if (result == (1<<max))
                break;
        }
        System.out.println(result);
    }
}









In C :





#include <stdio.h>
#define N 5000

int main() {
    int n, i, j, m, t, p2, a[N];
    scanf("%d", &n);
    for(i=0; i<n; i++) scanf("%d", &a[i]);
    m=0;
    for(i=0; i<n; i++) for(j=i+1; j<n; j++) if((a[i]^a[j])>m) m=a[i]^a[j];
    if(m==0) {
        printf("0\n");
        return 0;
    }
    for(p2=t=m; t; t>>=1) p2|=t;
    p2=(p2>>1)+1;
    for(i=0; i<n; i++) for(j=i+1; j<n; j++) if((a[i]^a[j])&p2) 
        if((a[i]^a[j])<m) m=a[i]^a[j];
    printf("%d\n", m);
    return 0;
}








In Python3 :






def solve(As) :
    a = max(As)
    b = -1
    while a > 0 :
        a >>= 1
        b += 1
    
    if b < 0 :
        return 0
    
    l = 1<<b
    while all(a & l for a in As) :
        l >>= 1
        
    if l == 0 :
        return 0
        
    Al = [a for a in As if not a & l]
    Au = [a for a in As if a & l]
    
    best = l << 1
    for al in Al :
        for au in Au :
            if al ^ au < best :
                best = al ^ au
               
    return best
    
    

n = int(input())
As = set(map(int,input().split()))
print(solve(As))