HackerRank Yet Another Minimax problem solution

In this HackerRank Yet Another Minimax problem solution we have given N non-negative integers. and we need to define the score for some permutations of length N to be the maximum of Api XOR Api+1 for 0 <= I < n – 1. find the permutation with the minimum possible score and print its score.

Problem solution in Python.

#!/bin/python3

import sys
from math import inf

def dec_to_bin(number):
    return bin(number)[2:]

def bin_to_dec(number):
    return int(number, 2)

def buildup_to_len(number, length):
    return '0' * (length - len(number)) + number

def get_max_len(arr):
    return len(dec_to_bin(max(arr)))
    
def get_min_len(arr):
    return len(dec_to_bin(min(arr)))

def anotherMinimaxProblem(a):
    res = inf
    arr_bin = []
    
    if max(a) == min(a) and max(a) == 0:
        return 0
    
    for el in a:
        arr_bin.append(dec_to_bin(el))
    
    # trim the elements
    while len(max(arr_bin, key=len)) == len(min(arr_bin, key=len)):
        arr_bin = [ el[:1].lstrip('1') + el[1:] for el in arr_bin ]
        arr_bin = [ el.lstrip('0') for el in arr_bin ]
        
    # build up the lesser elements
    max_len = len(max(arr_bin, key=len))
    #print("max len = {}".format(max_len))
    arr_bin = [ buildup_to_len(el, max_len) for el in arr_bin ]
    
    arr_zeros = []
    arr_ones = []
    
    for el in sorted(arr_bin):
        if el[0] == '0':
            arr_zeros.append(el)
        else:
            arr_ones.append(el)
    
    for el_z in arr_zeros:
        for el_o in arr_ones:
            res = min(res, bin_to_dec(el_z) ^ bin_to_dec(el_o))
    
    return res

if __name__ == "__main__":
    n = int(input().strip())
    a = list(map(int, input().strip().split(' ')))
    result = anotherMinimaxProblem(a)
    print(result)

Problem solution in Java.

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

public class YetAnotherMinimaxProblem {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] ar = new int[n];
        for (int i = 0; i < n; i++) ar[i] = scan.nextInt();
        
        Arrays.sort(ar);
        if ((ar[0] ^ ar[n - 1]) == 0) {
            System.out.println(0);
        } else {
            int high = Integer.highestOneBit(ar[0] ^ ar[n - 1]);
            int max = Integer.MAX_VALUE;
            for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {
                    if ((ar[i] & high) != (ar[j] & high)) max = Math.min(max, ar[i] ^ ar[j]);
                }
            }
            System.out.println(max);
        }
    }
}

Problem solution in C++.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cstdlib>
using namespace std;
typedef unsigned long ul;
int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int n ; cin >> n;
    ul a[n], b [n];
    bool allsame = true;
    for (int i = 0; i < n ; i++) {
        cin >> a[i];
        if (i != 0 && allsame && a[i] != a[i-1])
            allsame = false;
    }
    if (allsame) {
        cout<<"0";   
        return 0;
    }
    
    for (int k =31; k >=0; k--) {
        ul x = 1;
        vector<ul> z;
        vector<ul> o;
        bool zz = false, oo = false;
        for (int j = 1; j < k;j++)
            x<<=1;
        for (int i = 0; i < n; i ++) {
            if ((a[i] &x) == 0) {
                z.push_back(a[i]);
                zz = true;
            } else {
                o.push_back(a[i]);
                oo = true;
            }
        }
        if (!zz || !oo) 
               continue;
        ul m = numeric_limits<ul>::max();
        for (auto zi : z)
            for (auto oi : o)
                m = min(m, (zi^oi));
        cout<<m;
        return 0;
    }
   cout<<"0";
}

Problem solution in C.

#include <stdio.h>
#include <stdlib.h>

typedef char                I8;
typedef short                I16;
typedef int                    I32;
typedef long long            I64;
typedef unsigned char        U8;
typedef unsigned short        U16;
typedef unsigned int        U32;
typedef unsigned long long    U64;

I32 compareU32(const void *a, const void *b);
U32 getBoundedPow2(U32 u);
U32 trimMSBits(U32 **arr, const U16 size);
const U16 getBoundary(const U32 *arr, const U16 size, const U32 mask);
U32 getMinXOR(const U32 *arr, const U16 size, const U32 mask);
U32 XORBinarySearch(const U32* arr, I16 l, I16 r, U32 key);

I32 main(I32 argc, char** argv)
{
    U16 n;    scanf("%hu", &n);
    U32 *arr = (U32*)malloc(n * sizeof(U32));
    for(U16 i = 0; i < n; i++)
        scanf("%u", &arr[i]);

    U32 m = trimMSBits(&arr, n);
    printf("%un", m + getMinXOR(arr, n, m));

    free(arr);
    return 0;
}

I32 compareU32(const void *pa, const void *pb)
{
    return *(const U32*)pa - *(const U32*)pb;
}

U32 trimMSBits(U32 **arr, const U16 size)
{
    qsort(*arr, size, sizeof(U32), compareU32);
    U32 p = getBoundedPow2((*arr)[size - 1]), mask = p, minCount = 32;
    for(U16 i = 0, count = 0; i < size && minCount; i++, count = 0, mask = p)
    {
        while((*arr)[i] & mask)
        {
            mask >>= 1;
            count++;
        }

        if(count < minCount)
            minCount = count;
    }

    if(minCount)
    {
        U32 m = (mask >> (minCount - 1)) - 1;
        for(U16 i = 0; i < size; i++)
            (*arr)[i] &= m;
    }

    return mask >> minCount;
}

U32 getBoundedPow2(const U32 u)
{
    U32 mask = 0x40000000;
    while((u & mask) == 0 && mask)
        mask >>= 1;

    return mask;
}

const U16 getBoundary(const U32 *arr, const U16 size, const U32 mask)
{
    U16 l = 0;
    while(l < size && !(arr[l] & mask))
        l++;

    return l;
}

U32 getMinXOR(const U32 *arr, const U16 size, const U32 mask)
{
    if(!mask)
        return 0;

    const U16 boundary = getBoundary(arr, size, mask);
    U16 qIndex, l, r, end;
    U8 flag = (boundary >= ((size + (size % 2)) / 2)) ? 1 : 0;
    if(flag)
    {
        qIndex = boundary;
        end = size;
        l = 0;
        r = boundary - 1;
    }
    else
    {
        qIndex = 0;
        end = boundary;
        l = boundary;
        r = size - 1;
    }

    U32 min = 0xFFFFFFFF, key, XOR;
    while(min && qIndex < end)
    {
        key = (flag) ? arr[qIndex++] ^ mask : arr[qIndex++] | mask;
        XOR = XORBinarySearch(arr, l, r, key);
        if(XOR < min)
            min = XOR;
    }

    return min;
}

U32 XORBinarySearch(const U32* arr, I16 l, I16 r, U32 key)
{
    U32 XOR, min = 0xFFFFFFFF;
    U16 m;
    while(l <= r)
    {
        m = (l + r) / 2;
        XOR = key ^ arr[m];
        if(XOR < min)
            min = XOR;

        if(key == arr[m])
            break;
        else if(key < arr[m])
            r = m - 1;
        else if(key > arr[m])
            l = m + 1;
    }

    return min;
}