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("%u\n", 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;
}
0 Comments