Suppose that $\mbox{A}$ is a list of $n$ numbers $\{A_1,A_2,A_3,\ldots,A_n\}$ and $B=\{B_1,B_2,B_3,\ldots,B_n\}$ is a permutation of these numbers, we say B is K-Manipulative if and only if:

$M(B)=minimum(B_1\oplus B_2,B_2\oplus B_3,B_3\oplus B_4,...,B_{n-1}\oplus B_n,B_n\oplus B_1)$ is not less than $2^{K}$, where $\theta$ represents the XOR operator.

You are given $\mbox{A}$. Find the largest $\mbox{K}$ such that there exists a K-manipulative permutation $\mbox{B}$.

Input:

The first line is an integer $N$. The second line contains $N$ space separated integers - $A_1\ A_2\ \cdots\ A_n$.  

Output: 

The largest possible $\mbox{K}$, or $-1$ if there is no solution.

Constraints:  

$1<n<=100$ 
$0\leq A_i\leq10^9,where i\in[1,n]$ 

Sample Input 0
3
13 3 10

Sample Output 0
2

Explanation 0

Here the list $\mbox{A}$ is $\{13,3,10\}$. One possible permutation $B=\{10,3,13\}$. Here $M(B)=minimum\{B_1\oplus B_2,B_2\oplus B_3,B_3\oplus B_1\}=$ 

$\textit{minimum}\{10\oplus3,3\oplus13,13\oplus10\}=\textit{minimum}\{9,14,7\}=7$. 

So there exists a permutation $\mbox{B}$ of $\mbox{A}$ such that $M(B)$ is not less than $4=2^2$. However there does not exist any permutation $\mbox{B}$ of $\mbox{A}$ such that $M(B)$ is not less than $8=2^3$. So the maximum possible value of $\mbox{K}$ is $2$.

Sample Input 1
4
1 2 3 4

Sample Output 1
1

Explanation 1

Here the list $\mbox{A}$ is $\{1,2,3,4\}$. One possible permutation $B=\{1,2,4,3\}$. Here $M(B)=minimum\{B_1\oplus B_2,B_2\oplus B_3,B_3\oplus B_4\:B_4\oplus B_1\}=$ 

$minimum\{1\oplus2,2\oplus4,4\oplus3\:3\oplus1\}=minimum\{3,6,7,2\}=2$. 

So there exists a permutation $\mbox{B}$ of $\mbox{A}$ such that $M(B)$ is not less than $2=2^1$. However there does not exist any permutation $\mbox{B}$ of $\mbox{A}$ such that $M(B)$ is not less than $4=2^2$. So the maximum possible value of $\mbox{K}$ is $1$.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Bit manipulation


Solutions:
from collections import defaultdict

def topbits(value, k):
	return value & ~((1 << k) - 1)

def manipulative_exists(numlist, k):
	tbcount = defaultdict(int)
	for num in numlist:
		num_tb = topbits(num, k)
		tbcount[num_tb] += 1
	biggest = max(tbcount.values())
	return biggest * 2 <= len(numlist)

def highest_k(numlist):
	biggest_num = max(numlist)
	return biggest_num.bit_length() + 1

def my_main():
	listlen_split = input().split()
	listlen = int(listlen_split[0])
	numlist_split = input().split()
	numlist = [int(x) for x in numlist_split]
	maxk = highest_k(numlist)
	while maxk > 0 and (not manipulative_exists(numlist, maxk)):
		maxk = maxk - 1
	print(maxk)
my_main()


from collections import Counter

def main():
	n = int(input())
	a = [int(f) for f in input().split()]
	print(manip(a))

def manip(a):
	maxplace = 0
	hi = max(a)
	while hi >= 1 << maxplace:
		maxplace += 1
	maxplace -= 1
	while 2 * max(Counter((elt >> maxplace for elt in a)).values()) > len(a):
		maxplace -= 1
	return maxplace
main()


from collections import Counter

def solve(array):
	max_bits = 32
	for num_bits in range(max_bits, -1, -1):
		count = Counter([x >> num_bits for x in array])
		if all((value <= len(array) // 2 for value in count.values())):
			return num_bits
	return -1
n = int(input())
array = [int(x) for x in input().split()]
print(solve(array))


from collections import Counter
n = int(input())
array = [int(x) for x in input().split()]
count = {}
k = -1
for num_bits in range(32, -1, -1):
	count = Counter([x >> num_bits for x in array])
	isValid = True
	for (key, val) in count.items():
		if val > n / 2:
			isValid = False
			break
	if isValid:
		k = num_bits
		break
print(k)


n = int(input())
values = [int(x) for x in input().split()]
k = 0
while True:
	count = 0
	mask = 2 ** k - 1
	s = set()
	for x in values:
		v = x ^ x & mask
		if v > 0:
			count += 1
			s.add(v)
	if count < len(values) / 2 or (len(s) == 1 and len(s) < len(values) / 2):
		print(k - 1)
		break
	k += 1


from collections import Counter
input()
a = list(map(int, input().split()))
answer = -1
for i in range(32):
	if Counter((x >> i for x in a)).most_common(1)[0][1] <= len(a) // 2:
		answer = i
	else:
		break
print(answer)


import sys
import math
n = int(input().strip())
arr = [int(arr_i) for arr_i in input().strip().split(' ')]
flag = True
temp = 4294967296
for i in range(32, -1, -1):
	a = [x for x in arr if x >= temp]
	temp = temp >> 1
	if len(a) >= math.floor(n / 2):
		if n % 2 == 1:
			if len(a) == math.ceil(n / 2):
				print(i - 1)
				flag = False
		if flag:
			print(i)
		flag = False
		break
if flag:
	print(-1)


n = int(input())
A = [int(x) for x in input().split()]

def not_less_power2(x):
	i = -1
	p = 1
	while p <= x:
		p <<= 1
		i += 1
	return i
graph = [[not_less_power2(A[i] ^ A[j]) for i in range(n)] for j in range(n)]
max_power = min([max(line) for line in graph])

def hamiltonian_check(power):
	for node_neighbours in graph:
		if sum([1 for p in node_neighbours if p >= power]) < (n + 1) // 2:
			return False
	return True
power = -1
while power <= max_power:
	if not hamiltonian_check(power + 1):
		break
	power += 1
print(power)


n = int(input())
arr = list(map(int, input().split()))
answer = -1
for i in reversed(range(32)):
	ne = 0
	nl = 0
	ng = 0
	for x in arr:
		if x >> i & 1 == 1:
			ne += 1
		elif x.bit_length() - 1 < i:
			nl += 1
		else:
			ng += 1
	s = sorted([ne, nl, ng])
	exist = s[0] > 1
	best = 0
	diff = 10 ** 9
	for t in range(s[0] + 1):
		x = s[2] - t
		y = s[1] - (s[0] - t)
		if x - y >= 0 and x - y <= diff:
			best = t
			diff = x - y
	s[2] -= best
	s[1] -= s[0] - best
	s.sort()
	if exist and s[2] - s[1] <= 1 or (not exist and s[1] == s[2]):
		answer = i
		break
print(answer)


from collections import defaultdict
n = int(input())
x = [int(element) for element in input().split()]
answer = -1
for i in range(32, -1, -1):
	sub_x = [e // 2 ** i for e in x]
	count = defaultdict(lambda : 0)
	for e in sub_x:
		count[e] += 1
	if max(count.values()) <= n // 2:
		answer = i
		break
print(answer)


from collections import Counter as count
n = int(input())
a = list(map(int, input().split()))
assert len(a) == n and min(a) >= 0
k = 30
assert max(a) < 1 << k
while k >= 0:
	biggest = max(count([v >> k for v in a]).values())
	if 2 * biggest <= n:
		break
	k -= 1
print(k)


n = int(input())
k = n // 2
num0 = 0
num1 = 0
maxlength = 0
A = list(map(int, input().strip().split(' ')))
B = []
for i in range(n):
	x = bin(A[i])[2:]
	x = x[::-1]
	if len(x) > maxlength:
		maxlength = len(x)
	B += [x]
L = maxlength - 1
total = [i for i in range(n)]
ans = 0
while L >= 0:
	num0 = []
	num1 = []
	temp0 = 0
	temp1 = 0
	for i in total:
		if len(B[i]) <= L:
			num0 += [i]
			temp0 += 1
		elif B[i][L] == '1':
			num1 += [i]
			temp1 += 1
		else:
			num0 += [i]
			temp0 += 1
	if max(temp0, temp1) <= k:
		ans = L
		break
	elif temp0 > temp1:
		total = []
		for i in range(temp0):
			total += [num0[i]]
	else:
		total = []
		for i in range(temp1):
			total += [num1[i]]
	L = L - 1
print(ans)


N = int(input())
A = [int(x) for x in input().split()]
K = 0
for x in A:
	while x > 2 << K:
		K += 1
while K >= 0:
	bins = {}
	for x in A:
		y = x >> K
		bins[y] = bins.get(y, 0) + 1
	if max(bins.values()) <= N >> 1:
		break
	K -= 1
print(K)


from collections import Counter

def is_possib(k, xs):
	return Counter(xs).most_common()[0][-1] <= len(xs) // 2
n = int(input())
xs = [int(x) for x in input().split()]
for k in range(31, -1, -1):
	if is_possib(k, [x >> k for x in xs]):
		print(k)
		break


from collections import Counter

def check(A, k):
	c = Counter([i[:-k] for i in A])
	return c.most_common(1)[0][1] * 2 <= len(A)

def main():
	n = int(input())
	A = list(map(lambda x: bin(int(x))[2:], input().split()))
	for k in reversed(range(1, 31)):
		if check(A, k):
			return k
	return 0
print(main())


import sys
import math
data = sys.stdin.readlines()
A = [int(i) for i in data[1].split()]
n = len(A)
bitlist = []
for i in range(0, math.floor(math.log(max(A)) / math.log(2)) + 1):
	row = []
	for j in range(0, len(A)):
		row.append(A[j] % 2)
		A[j] = A[j] // 2
	bitlist.append(row)
exsbits = []
total = 0
K = 0
for i in range(len(bitlist) - 1, -1, -1):
	(onecount, zerocount) = (0, 0)
	for j in range(0, n):
		needcount = True
		for r in range(len(bitlist) - 1, i, -1):
			if bitlist[r][j] != exsbits[len(bitlist) - 1 - r]:
				needcount = False
				break
		if needcount:
			if bitlist[i][j] == 1:
				onecount = onecount + 1
			else:
				zerocount = zerocount + 1
	if 2 * min(zerocount, onecount) + total >= n:
		K = i
		break
	elif zerocount < onecount:
		exsbits.append(1)
	else:
		exsbits.append(0)
	total = total + 2 * min(onecount, zerocount)
print(K)


from collections import defaultdict

def read_tokens():
	return input().strip().split(' ')

def read_ints():
	return [int(s) for s in read_tokens()]
(n,) = read_ints()
a = read_ints()

def good(a):
	cnt = defaultdict(int)
	for x in a:
		cnt[x] += 1
	return max(cnt.values()) * 2 <= len(a)

def f(a):
	for k in reversed(range(32)):
		b = [x // 2 ** k for x in a]
		if good(b):
			return k
	return -1
print(f(a))


(CSM, CS, mp, n, t, data) = ([0] * 32, [0] * 32, 0, int(input()), 30, sorted([int(x) for x in input().split(' ')]))
for x in data:
	while x >= 1 << mp:
		mp += 1
	CS[mp] += 1
for k in range(30, -1, -1):
	CSM[k] = CSM[k + 1] + CS[k + 1]

def check(ck, tv):
	if not CSM[ck + 1]:
		return False
	if abs(CSM[ck + 1] - CS[ck]) <= tv:
		return True
	return check(ck + 1, CSM[ck + 1] - CS[ck] - tv)
while t >= 0:
	if n - CSM[t] * 2 <= 0 and check(t, CSM[k] * 2 - n):
		break
	t -= 1
print(t)


from collections import Counter
KMAX = 29

def main():
	N = int(input())
	A = list(map(int, input().split()))
	for K in range(KMAX, -1, -1):
		C = Counter((a >> K for a in A))
		m = max(C.values())
		if m <= N // 2:
			break
	print(K)
main()


N = int(input().strip())
As = list(map(int, input().strip().split()))
MaxCount = (N - N % 2) // 2
ListBits = [[] for _ in range(N)]
ListPar = [0] * N
for (I, A) in enumerate(As):
	while A > 0:
		if A % 2 > 0:
			ListBits[I].append(1)
		else:
			ListBits[I].append(0)
		A = A // 2
	while len(ListBits[I]) < 32:
		ListBits[I].append(0)
for B in range(31, -1, -1):
	Counts = {}
	for I in range(N):
		Par = ListPar[I] = 2 * ListPar[I] + ListBits[I][B]
		if Par not in Counts.keys():
			Counts[Par] = 0
		Counts[Par] += 1
	for V in Counts.values():
		if V > MaxCount:
			break
	else:
		print(B)
		exit()
print(-1)


from collections import Counter
input()
a = list(map(int, input().split()))
answer = -1
for i in range(32):
	if Counter((x >> i for x in a)).most_common(1)[0][1] <= len(a) // 2:
		answer = i
	else:
		break
print(answer)


N = int(input())
A = list(map(int, input().split(' ')))
cnt = 0
for E in A:
	if E == A[0]:
		cnt += 1
if cnt == N:
	print(-1)
else:
	ans = -1
	while True:
		d = {}
		for E in A:
			if E in d:
				d[E] += 1
			else:
				d[E] = 1
		end = False
		for (E, cnt) in d.items():
			if cnt > N // 2:
				end = True
		if end:
			break
		for i in range(len(A)):
			A[i] >>= 1
		ans += 1
	print(ans)


import math
import os
import random
import re
import sys
from collections import Counter
input()
a = list(map(int, input().split()))
answer = -1
for i in range(32):
	if Counter((x >> i for x in a)).most_common(1)[0][1] <= len(a) // 2:
		answer = i
	else:
		break
print(answer)


from collections import Counter
input()
a = list(map(int, input().split()))
answer = -1
for i in range(32):
	if Counter((x >> i for x in a)).most_common(1)[0][1] <= len(a) // 2:
		answer = i
	else:
		break
print(answer)


from collections import Counter
input()
a = list(map(int, input().split()))
answer = -1
for i in range(32):
	if Counter((x >> i for x in a)).most_common(1)[0][1] <= len(a) // 2:
		answer = i
	else:
		break
print(answer)


from collections import Counter
input()
a = list(map(int, input().split()))
answer = -1
for i in range(32):
	if Counter((x >> i for x in a)).most_common(1)[0][1] <= len(a) // 2:
		answer = i
	else:
		break
print(answer)


from collections import Counter
input()
a = list(map(int, input().split()))
answer = -1
for i in range(32):
	if Counter((x >> i for x in a)).most_common(1)[0][1] <= len(a) // 2:
		answer = i
	else:
		break
print(answer)


from collections import Counter
input()
a = list(map(int, input().split()))
answer = -1
for i in range(32):
	if Counter((x >> i for x in a)).most_common(1)[0][1] <= len(a) // 2:
		answer = i
	else:
		break
print(answer)


from collections import Counter
input()
a = list(map(int, input().split()))
answer = -1
for i in range(32):
	if Counter((x >> i for x in a)).most_common(1)[0][1] <= len(a) // 2:
		answer = i
	else:
		break
print(answer)


import math
import os
import random
import re
import sys
from collections import Counter
input()
a = list(map(int, input().split()))
answer = -1
for i in range(32):
	if Counter((x >> i for x in a)).most_common(1)[0][1] <= len(a) // 2:
		answer = i
	else:
		break
print(answer)


from collections import Counter

def star():
	input()
	saiteja = list(map(int, input().split()))
	asgdgdgsds = -1
	for i in range(32):
		if Counter((x >> i for x in saiteja)).most_common(1)[0][1] <= len(saiteja) // 2:
			asgdgdgsds = i
		else:
			break
	print(asgdgdgsds)
star()


from collections import defaultdict

def topbits(value, k):
	return value & ~((1 << k) - 1)

def manipulative_exists(numlist, k):
	tbcount = defaultdict(int)
	for num in numlist:
		num_tb = topbits(num, k)
		tbcount[num_tb] += 1
	biggest = max(tbcount.values())
	return biggest * 2 <= len(numlist)

def highest_k(numlist):
	biggest_num = max(numlist)
	return biggest_num.bit_length() + 1

def my_main():
	listlen_split = input().split()
	listlen = int(listlen_split[0])
	numlist_split = input().split()
	numlist = [int(x) for x in numlist_split]
	maxk = highest_k(numlist)
	while maxk > 0 and (not manipulative_exists(numlist, maxk)):
		maxk = maxk - 1
	print(maxk)
my_main()


from collections import Counter
input()
a = list(map(int, input().split()))
answer = -1
for i in range(32):
	if Counter((x >> i for x in a)).most_common(1)[0][1] <= len(a) // 2:
		answer = i
	else:
		break
print(answer)