Problem:
 Score : 400 points    Problem Statement You are given N non-negative integers A_1, A_2, ..., A_N and another non-negative integer K .  For a integer X between 0 and K (inclusive), let f(X) = (X XOR A_1)  +  (X XOR A_2)  +  ...  +  (X XOR A_N) .  Here, for non-negative integers a and b , a XOR b denotes the bitwise exclusive OR of a and b .  Find the maximum value of f .   What is XOR?  The bitwise exclusive OR of a and b , X , is defined as follows:   When X is written in base two, the digit in the 2^k 's place ( k \geq 0 ) is 1 if, when written in base two, exactly one of A and B has 1 in the 2^k 's place, and 0 otherwise.   For example, 3 XOR 5 = 6 . (When written in base two: 011 XOR 101 = 110 .)

Solution (Python):
N,K = map(int, input().split())
A = list(map(int,input().split()))

binK = bin(K)[2:]
maC = 0

B = [0 for _ in [0]*40]

for i in range(N):
    C = bin(A[i])[2:][::-1]
    maC = max(maC,len(C))
    for j in range(len(C)):
        B[j] = B[j] + int(C[j])
        
an = 0

PPP = max(len(binK),maC)
KK = [int(t < N/2) for t in B[:len(binK)][::-1]]

for k in range(PPP):
    if k < len(binK):
        an = an + max(B[k], N-B[k])*(2**k)
    else:
        an = an + B[k]*(2**k)











for l in range(len(binK)):
    if int(binK[l]) > KK[l]:
        break
    if int(binK[l]) < KK[l]:
        ll = len(KK) - l -1
        an = an - max(B[ll], N-B[ll])*(2**ll) + min(B[ll], N-B[ll])*(2**ll)
            

print(an)

Solution (Python):




def hard_log2(N):
    
    r = 1
    l = 0
    while N >= 2*r:
        r *= 2
        l += 1
    return r, l

def maximize_simple(r_list, K, N):
    if K == 0:
        return 0
    R = 0
    L, M = hard_log2(K)
    for i in range(M+1):
        R += max(r_list[i], N - r_list[i])*(2**i)
        
    return R

def maximize(r_list, K, N):
    
    if K == 0:
        return 0
    
    L, M = hard_log2(K)
    
    if r_list[M] >= N - r_list[M]:
        return maximize_simple(r_list, L-1, N)+r_list[M]*(2**M)
    else:
        R = (N-r_list[M])*(2**M)
        m = M - 1
        while 2**m > K-L and m >=0:
            R += r_list[m]*(2**m)
            m -= 1
        
        return max(maximize(r_list, K-L, N)+R, maximize_simple(r_list, L-1, N)+r_list[M]*(2**M))

def main_d(A_list, N, K):
    r_list = [0]*41
    for i in range(41):
        for A in A_list:
            if (A % 2**(i+1)) >= 2**i:
                r_list[i] += 1
    if K == 0:
        R = 0
        for i in range(41):
            R += r_list[i]*(2**i)
        return R
    else:
        L, M = hard_log2(K)
        R = 0
        for i in range(M+1, 41):
            R += r_list[i]*(2**i)
        return R + maximize(r_list, K, N)
    

if __name__ == "__main__":
    N, K = map(int, input().split())
    A_list = list(map(int, input().split()))
    res = main_d(A_list, N, K)
    print(res)

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))

c=[[0 for _ in range(2)] for _ in range(64)]

for i in range(n):
    for j in range(60):
        c[j][a[i]>>j&1] += 1
x=0
for i in range(59,-1,-1):
    if(c[i][0] > c[i][1] and x|(1<<i) <= k):
        x |= 1<<i

sum = 0
for i in range(n):
    sum += a[i]^x
print(sum)

Solution (Python):

n, k = map(int, input().split())
a = input().split()
a = [int(m) for m in a]

bina = [str(bin(m)) for m in a]
lenbina = [len(str(bin(m))) for m in a]

m = 61
x = 0
X = 0
y = 0
tmp0 = 0
tmp1 = 0
ff = [0 for _ in range(n)]
for v in range(m - 1, -1, -1):
    for i in range(n):
        if len(bina[i]) - 2 > v:
            if ff[i] == 0:
                ff[i] = 1
                lenbina[i] = v + 2
            t = int(bina[i][lenbina[i] - v])
            if int(bina[i][lenbina[i] - v]) ^ x == x:
                tmp0 += 1
            else:
                tmp1 += 1
        else:
            
            tmp0 += 1
    if tmp0 > tmp1:
        X += 2 ** v
        y += 2 ** v
        if X > k:
            X -= 2 ** v
    tmp0 = 0
    tmp1 = 0

ans = 0
for i in range(n):
    ans += a[i] ^ X
print(ans)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))

K = format(K, '040b')
A = [format(a, '040b') for a in A]

max_flg = 0
ans = ''
for index, i in enumerate(list(K)):
    if i == '1':
        num_1 = 0
        for a in A:
            if a[index] == '1':
                num_1 += 1
        if num_1 >= int(N/2) + 1:
            ans += '0'
            max_flg = 1
        else:
            ans += '1'
    else:
        if i == '0' and max_flg == 0:
            ans += '0'
        elif i == '0' and max_flg == 1:
            num_1 = 0
            for a in A:
                if a[index] == '1':
                    num_1 += 1
            if num_1 >= int(N/2) + 1:
                ans += '0'
            else:
                ans += '1'
ans2 = 0
for a in A:
    ans2 += int(ans, 2) ^ int(a, 2)
print(ans2)

Solution (Python):
import sys
import math





def saiki(k, bit):
    if bit == -1:
        return 0

    
    if k < (1 << bit):
        return onecounts[bit] * (1 << bit) + saiki(k, bit - 1)

    
    
    if zerocounts[bit] < onecounts[bit]:
        return bestsum[bit]

    
    

    bitscore = zerocounts[bit] * (1 << bit) + saiki(k - (1 << bit), bit - 1)
    nonbitscore = onecounts[bit] * (1 << bit) + bestsum[bit - 1]
    return max(bitscore, nonbitscore)


n, k = list(map(int, input().split()))

a = list(map(int, input().split()))

if k == 0:
    print(sum(a))
    quit()

sum = 0

zerocounts = [0] * 52
onecounts = [0] * 52
bestsum = [0] * 52

x = 0


for bit in reversed(range(50)):
    count = 0
    for i in range(n):
        if a[i] & (1 << bit) > 0:
            count += 1
    onecounts[bit] = count
    zerocounts[bit] = n - count

sum = 0
for bit in range(50):
    cc = max(zerocounts[bit], onecounts[bit])
    sum += (1 << bit) * cc
    bestsum[bit] = sum

sum = saiki(k, 50)

print(sum)

Solution (Python):

import numpy as np

def solve():
    N, K = map(int, input().split())
    A = map(int, input().split())
    X = np.arange(K.bit_length())
    Y = np.zeros_like(X)
    Z = 0
    for a in A:
        Y += (a>>X)&1
        Z += a
    Y = np.maximum(Y, N-Y)-Y
    Y *= (1<<X)
    L = (K>>X)&1
    W = (Y*L).sum()
    for k in range(1, K.bit_length()):
        if L[k] == 1:
             L[:k+1]= ((((1<<k)-1)>>X)&1)[:k+1]
             W = max(W, (Y*L).sum())

    res = Z+W
    return str(res)
if __name__ == '__main__':
    print(solve())

Solution (Python):
import math
n,k = map(int, input().split())
a = list(map(int, input().split()))
c = int(math.log2(max(k,max(a)))+1)
d = [0]*c
for i in a:
  b = format(i, 'b')
  for j,l in enumerate(b[::-1]):
    if l == "1":
      d[j] += 1
ans = 0
for i,j in enumerate(d[::-1]):
  zero = n - j
  one = j
  if k >= 2 ** (c-i-1):
    if zero > one:
      ans += zero * (2 ** (c-i-1))
      k -= 2 ** (c-i-1)
    else:
      ans += one * (2 ** (c-i-1))
  else:
    ans += one * (2 ** (c-i-1)) 
print(ans)

Solution (Python):
N, K = map(int, input().split())
A =list(map(int, input().split()))
k = bin(K)[2:]

def add_zero(text):
    if len(text) < len(k):
        mozi = ""
        for i in range(len(k) - len(text)):
            mozi += "0"
        return mozi + text
    else:
        return text

B = [bin(i)[2:] for i in A ]
B = list(map(add_zero, B))

ans_li = []
for index, i in enumerate(k):
    if i == "1":
        str = ""
        for j in range(len(k)-index-1):
            count = 0
            for l in B:
                if l[-j-1] == "1":
                    count += 1
            if count > len(B) - count:
                str = "0" + str
            else:
                str = "1" + str
        ans_li.append(k[:index] + "0" + str)

ans_li.append(k)
ans_li2 = [int("0b"+i, 2) for i in ans_li]
max_score = 0
for i in ans_li2:
    score = 0
    for j in A:
        score += i^j
    max_score = max(score, max_score)

print(max_score)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))

binlen = 0
while 2 ** binlen <= K:
    binlen += 1
binlen -= 1

if binlen < 0:
    print(sum(A))
    exit()

bitcount = [0] * (len(bin(max(A))) - 2)
for a in A:
    for i, s in enumerate(bin(a)[::-1][:-2]):
        if s == "1":
            bitcount[i] += 1

maxn = 2 ** binlen
mid = N / 2

for i in range(binlen + 1):
    if i < len(bitcount):
        if bitcount[i] < mid and i != binlen:
            maxn += 2 ** i
        elif bitcount[i] > mid and i == binlen:
            maxn -= 2 ** i
    elif i != binlen:
        maxn += 2 ** i

pos = 0
while maxn > K:
    if bin(maxn)[2:][pos] == "1" and bin(K)[2:][pos] == "0":
        maxn -= 2 ** (len(bin(maxn)) - 3 - pos)
    pos += 1

print(sum([maxn ^ a for a in A]))

Solution (Python):
from math import log
import sys
n,k= map(int, raw_input().split())
a = map(int, raw_input().split())
if k is 0:
	ans = 0
	for i in range(n):
		ans += a[i]
	print(ans)
else:
	logk = int(log(k,2)) + 1
	num = []
	for i in range(logk):
		num.append(0)
	for i in range(n):
		memo = a[i]
		for j in range(logk):
			if memo%2 == 0:
				num[j] += 1
			else:
				num[j] -= 1
			memo = int(memo/2)
	ans = 0
	ans_m = -1
	suml = []
	suml.append(max(num[0],0))
	for i in range(logk-1):
		if num[i+1] > 0:
			suml.append(suml[i] + pow(2,(i+1))*num[i+1])
		else:
			suml.append(suml[i])
	num.reverse()
	suml.reverse()
	now = 0
	for i in range(logk):
		if k >= pow(2,(logk-1-i)):
			if i+1 < logk and ans < now + suml[i+1]:
				ans = now + suml[i+1]
			k -= pow(2,(logk-1-i))
			now += pow(2,(logk-1-i)) * num[i]
	ans = max(ans,now)
	for i in range(n):
		ans += a[i]
	print(ans)

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
M=max(a)
K=str(format(k,'b'))
MM=str(format(M,'b'))
x=max(len(K),len(MM))
K=str(format(k,'b').zfill(x))
l=[]
for i in range(n):
  l.append(str(format(a[i],'b').zfill(x)))

ctMz=0
for z in range(len(K)):
  if K[z]=='0':
    ctMz+=1
  else:
    break

l2=[]


ct=0
for j in range(x):
  ctz=0
  cto=0
  for m in range(n):
    if l[m][j]=='0':ctz+=1
    else:cto+=1
  if j+1<=ctMz:
    ct+=(2**(x-j-1))*cto
    l2.append('0')
  else:
    if ctz>cto:
      ct+=(2**(x-j-1))*ctz
      l2.append('1')
    else:
      ct+=(2**(x-j-1))*cto
      l2.append('0')
      
y=int(''.join(l2))
y2=int(str(format(k,'b')))
if y2>=y:
  print(ct)
else:
  l2=['0' for aa in range(x)]
  ct=0
  for j in range(x):
    ctz=0
    cto=0
    for m in range(n):
      if l[m][j]=='0':ctz+=1
      else:cto+=1
    if j+1<=ctMz:
      ct+=(2**(x-j-1))*cto
      l2[j]='0'
    else:
      if ctz>cto:
        l2[j]='1'
        if y2>=int(''.join(l2)):
          ct+=(2**(x-j-1))*ctz
        else:
          ct+=(2**(x-j-1))*cto
          l2[j]='0'
      else:
        ct+=(2**(x-j-1))*cto
        l2[j]='0'
  print(ct)

Solution (Python):

"""
Created on Sun Feb  3 21:22:26 2019

@author: Yamazaki Kenichi
"""

N,K = map(int,input().split())
A = list(map(int,input().split()))
A = [bin(i) for i in A]

B = [0 for i in range(44)]

for i in range(N):
    for j in range(len(A[i])):
        if A[i][-1-j] == '1':
            B[j] += 1
Ans = []
c = 0
for i in range(44):
    if i <= len(bin(K))-3:
        Ans.append(1) if B[i]<=N//2 else Ans.append(0)
    else:
        Ans.append(0)

for i in range(0,len(bin(K))-2):
    if int(bin(K)[i+2]) - Ans[len(bin(K))-3-i] == -1:
        Ans[len(bin(K))-3-i] = 0
    elif int(bin(K)[i+2]) - Ans[len(bin(K))-3-i] == 1:
        break

ans = 0
for i in range(44):
    ans += pow(2,i)*(B[i]) if Ans[i] == 0 else pow(2,i)*(N-B[i])
print(ans)

Solution (Python):
N, K = [int(_) for _ in input().split()]

d = K.bit_length()
fmt = "0{}b".format(d)

Aa = [int(_) for _ in input().split()]
A = [format(int(_), fmt)[-d:] for _ in Aa]

X = 0
for i in range(d):

    count = 0
    temp = 1 << (d - i - 1)

    if X + temp > K:
        continue

    for j in range(N):
        if A[j][i] == '0':
            count -= 1
        else:
            count += 1
    if count < 0:
        X += temp

ans = 0
for ai in Aa:
    ans += (ai ^ X)

print(ans)

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
t,ans=2**40,0
while t:
	c=sum([(a[i]&t)//t for i in range(n)])
	if k<t or c*2>=n:
		ans+=t*c
	else:
		ans+=t*(n-c)
		k -= t
	t //= 2
print(ans)

Solution (Python):
def solve(n, k, al):
    bin_k = format(k,"b")
    len_k = len(bin_k)
    
    
    answer = 0
    enable_one = False
    zero_limit = n // 2
    for i in range(len_k,-1,-1):
        bit = 1 << i
        answer = answer << 1
        if enable_one or ((k & bit) != 0):
            
            zero_count = 0
            for e in al:
                if (e & bit) == 0:
                    zero_count += 1
            if zero_count > zero_limit:
                answer += 1
            else:
                enable_one = True
    

    s = 0
    for e in al:
        s = s + (answer ^ e)
    print(s)

def main():
    n, k = map(int, input().split())
    al = list(map(int, input().split()))
    solve(n, k, al)

main()

Solution (Python):
n, k = map(int, input().split())
a = list(map(int,input().split()))

bin_digit = [0]*50
for ai in a:
    i = 0
    bin_ai = bin(ai)
    for i in range(len(bin_ai)-2):
        if bin_ai[-1-i] == '1':
            bin_digit[i] += 1
        i += 1

bin_k = list(map(int, bin(k)[-1:1:-1]))
length_k = len(bin_k)
x_k = [None]*length_k
for i in range(length_k):
    if 2*bin_digit[i]>=n:
        x_k[i] = 0
    else:
        x_k[i] = 1

for i in range(length_k-1,-1,-1):
    if x_k[i]>bin_k[i]:
        x_k[i] = 1-x_k[i]
    elif x_k[i]<bin_k[i]:
        break

x = sum(x_k[i]*2**i for i in range(len(x_k)))
ans = sum(x^ae for ae in a)
print(ans)

Solution (Python):
import numpy as np

n, k = map(int, input().split())
lst = list(map(int, input().split()))

def factorize(i):
    lst = []
    while i >= 1:
        if i % 2 == 1:
            lst.append(1)
        else:
            lst.append(0)
        i = i // 2
    lst.reverse()
    if len(lst) < 45:
        lst = [0] * (45 - len(lst)) + lst
    return lst

array = np.zeros((n,45))
for n, i in enumerate(lst):
    array[n] = factorize(i)

    
col_sum = array.sum(axis=0)

ans_lst = []
for i in col_sum:
    if i > n//2:
        ans_lst.append(0)
    else:
        ans_lst.append(1)
        
ans_lst

ans = 0
for n, i in enumerate(ans_lst):
    new_ans = ans + i * 2**(44-n)
    if new_ans > k:
        continue
    else:
        ans = new_ans
        
max_f = 0
for i in lst:
    max_f += ans ^ i
print(max_f)

Solution (Python):
N, K = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]


def solve():
    ans = 0
    bigable = True

    for i in range(41)[::-1]:

        tmp = 1 << i
        sum_ = 0
        for a in A:
            sum_ += (tmp & a > 0)

        
        if bigable and K & tmp == 0:
            ans += sum_ * tmp
            continue

        
        if sum_ >= N / 2:
            ans += sum_ * tmp
            if K & tmp > 0:
                bigable = False
        else:
            ans += (N - sum_) * tmp

    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
N, K = map(int,input().split())
A = sorted(list(map(int,input().split())))

p = 0
while 2**(p+1) < max(max(A),K):
    p += 1

D = [0]*(p+1)

for k in range(N):
    s = (bin(A[k])[2:]).zfill(p+1)
    for d in range(p+1):
        if s[d] == "0":
            D[d] -= 1
        else:
            D[d] += 1

m = 0
for k in range(p+1):
    if D[k] <= 0:
        if m + 2**(p-k) <= K:
            m += 2**(p-k)

ans = 0
for k in range(N):
    ans += m^A[k]
print(ans)

Solution (Python):
N,K=map(int,input().split())

A=list(map(int,input().split()))

answer=0
if K==0:
  for i in A:
    answer+=0^i
  print(answer)
  exit()
  

ketalimit=1
jou=1

while 2**jou-1<K:
  ketalimit+=1
  jou+=1

ketaone=[0]*44
for i in A:
  bini=format(i,'b')
  stri=str(bini)
  for j in range(len(stri)):
    ketaone[-j-1]+=int(stri[-j-1])

answerN=0
for i in range(ketalimit+1,0,-1):
  if ketaone[-i]<=int(N/2) and answerN+2**(i-1)<=K:
  	answerN+=2**(i-1)
for i in A:
  answer+=(i^answerN)
print(answer)

Solution (Python):
n,k = map(int, input().split())
a=list(map(int, input().split()))
cnt_bit=[0]*42
for ai in a:
  bit=1
  for i in range(0,42):
    if ai&bit==bit:
      cnt_bit[i]+=1
    bit*=2

ans=0
cur_k=0
bit=2**41
for cnt in cnt_bit[::-1]:
  if cur_k+bit<=k:
    if cnt>n-cnt:
      ans+=bit*cnt
    else:
      ans+=bit*(n-cnt)
      cur_k+=bit
  else:
    ans+=bit*cnt
  bit//=2
    
print(ans)

Solution (Python):
N, K = map(int, input().split(" "))
A = list(map(int, input().split(" ")))






x = 0
for i in range(39, -1, -1):
    b = sum((a>>i)%2 for a in A)*2 < N
    
    if x+(b<<i) <= K:
        x += (b<<i)
    else:
        continue






print(sum(x^a for a in A))

Solution (Python):
N,K=list(map(int,input().split()))

A=list(map(int,input().split()))

bit_list = [0 for i in range(50)]
for i in range(N):
    a = A[i]
    for j in range(50):
        if a%2==1:
            bit_list[j]+=1
        a=a//2
        if a==0:
            break

bitk=bin(K)[2:]
lenk = len(bitk)
bitk=bitk[::-1]

maxscore=0
for i in range(len(bitk)):
    patA=0
    if bitk[i]=="1":
        first=i
        for j in range(50):
            if j<first:
                patA+=max(N-bit_list[j],bit_list[j])*(2**j)
            elif j==first:
                patA+=bit_list[j]*(2**j)
            elif j<lenk:
                if bitk[j]=="0":
                    patA+=bit_list[j]*(2**j)
                else:
                    patA+=(N-bit_list[j])*(2**j)
            else:
                patA+=bit_list[j]*(2**j)


    maxscore=max(patA,maxscore)

patB=0
for i in range(50):
    patB+=bit_list[i]*(2**i)
patC=0
for i in range(50):
    if i<lenk:
        if bitk[i]=="0":
            patC+=bit_list[i]*(2**i)
        else:
            patC+=(N-bit_list[i])*(2**i)
    else:
        patC+=bit_list[i]*(2**i)

print(max(maxscore,patB,patC))

Solution (Python):
N, K = map(int, input().split())
A = sorted([int(a) for a in input().split()])

X = [0] * 45
for i in range(N):
    b = bin((1<<45)+A[i])
    
    for j in range(45):
        if b[-j-1] == "1":
            X[j] += 1


ans = 0
for i in range(45):
    if 1<<i > K:
        break
    ans += max(X[i], N - X[i]) << i
    
def intlog2(n):
    if n <= 0:
        return -1
    i = 0
    while 2**i <= n:
        i += 1
    return i-1
def calc(k, t):
    
    if t<0:
        return 0
    if k == 0 or intlog2(k) < t:
        return X[t] * (2**t) + calc(k, t-1)
        
    a = k+1
    while a%2==0:
        a//=2
    if a == 1:
        ret = 0
        for i in range(45):
            if 1<<i > k:
                break
            ret += max(X[i], N - X[i]) << i
            
        return ret
    else:
        ll = intlog2(k)
        kk = 2**ll
        ret = kk * X[ll] + calc(kk-1, t-1)
        if X[ll] < N - X[ll]:
            ret2 = kk * (N - X[ll]) + calc(k-kk, t-1)
            ret = max(ret, ret2)
            
        return ret
        
if K == 0:
    print(sum(A))
else:
    print(calc(K, 44))

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))

binK = str(bin(K))[2:]
lenbinK = len(binK)

binA = [str(bin(x))[2:] for x in A]
lenbinA = [len(x) for x in binA]

maxlenbinA = max(lenbinA)
maxzentai = max(lenbinK, maxlenbinA)
binA0 = [x.zfill(maxzentai) for x in binA]
binK0 = binK.zfill(maxzentai)


kosu1 = [0 for i in range(maxzentai)]
for i in range(maxzentai):
    for strbinA in binA0:
        if strbinA[i] == '1':
            kosu1[i] += 1

count = 0
flag = False
for i in range(maxzentai):
    if flag:
        count += max(kosu1[i], N - kosu1[i]) * (2 ** (maxzentai - 1 - i))
    else:
        if binK0[i] == '1':
            count += max(kosu1[i], N - kosu1[i]) * (2 ** (maxzentai - 1 - i))
            if kosu1[i] >= N-kosu1[i]:
                flag = True
        elif binK0[i] == '0':
            count += kosu1[i] * (2 ** (maxzentai - 1 - i))
print(count)

Solution (Python):
from math import log2

N, K = map(int, input().split())
a = list(map(int, input().split()))
sa = sum(a)

if sa == 0:
    print(K * N)
    exit()

b = [0 for _ in range(int(log2(max(sa, K))) + 1)]


ls = int(log2(sa))


for aa in a:
    for i in range(ls + 1):
        
        if (aa >> i) & 1 == 1:
            
            b[i] += 1


x = []
if K > 0:
    for i in range(int(log2(K)) + 1):
        t = N - 2 * b[i]
        if t > 0:
            x.append((1 << i, t * (1 << i)))
            

    x = sorted(x, key=lambda xx: xx[1], reverse=True)


sx = 0
st = 0
for xx in x:
    if sx + xx[0] <= K:
        sx += xx[0]
        st += xx[1]

ans = sa + st
print(ans)

Solution (Python):



n,k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]

q = [0]*45
qm = [0]*45

for i in range(45):
    z=0
    for aa in a:
        if (aa&(2**i))==0:
            z+=1
    q[i] = z
    qm[i] = max(z,n-z)




def keta(nn):
   r = 0
   while nn:
       nn = nn// 2
       r+=1
   return r


def fmax(x,dg):
    if dg < 0:
        return 0
    ke=keta(x)-1
    if ke<dg:
        return fmax(x,dg-1)+(2**dg)*(n-q[dg])
    keee=keta(x-2**ke)
    c = fmax(x-2**ke,dg-1) + (2**dg)*q[dg]
    d = sum([(2**i)*qm[i] for i in range(ke)])+(2**ke)*(n-q[ke])

    return max(c, d)





print(fmax(k,44))

Solution (Python):
N,K = map(int,input().split())
A = list(map(int,input().split()))

bs = [0] * 40
for a in A:
    for k in range(40):
        if a&(1<<k):
            bs[k] += 1

x = 0
for k in range(39,-1,-1):
    if x + (1<<k) > K: continue
    if bs[k] < (N+1)//2:
        x += (1<<k)

ans = 0
for a in A:
    ans += x^a
print(ans)

Solution (Python):
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict, Counter
from bisect import bisect

setrecursionlimit(10**7)

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

N, K = reads()
A = reads()

def f(X):
  return sum(X ^ a for a in A)

maj = 0
for j in range(41):
  if sum(a & (1 << j) > 0 for a in A) <= N // 2:
    maj |= (1 << j)

ans = (f(K), K)
for i in range(45):
  if K & (1 << i) == 0:
    continue
  X = K & ((~0) << (i+1)) | (maj & ((1 << i) - 1))
  ans = max(ans, (f(X), X))
print(ans[0])

Solution (Python):
"""
方針　各桁を0にするか1にするかは独立に考えてよい

K = 10101 の時
0か1か好きに選べる桁をfとして
* X = 10101
* X = 10100
* X = 100ff
* X = 0ffff
を試し、最大になるものを選ぶ

2**39 < 10**12 < 2**40　なので40桁について考え
fのときどっちを選ぶとよいかを前計算しておく"""


def  inpl(): return list(map(int, input().split()))

N, K = inpl()
A = inpl()

L = [0]*40  
for i in range(N):
    for j in range(40):
        L[j] += (A[i] >> j)&1

default = [(N - L[i]) * (2**i) if (K>>i)&1 == 1 else L[i] * (2**i) for i in range(40)]
free = [max(L[i] * (2**i), (N-L[i])*(2**i)) for i in range(40)]

ans = sum([K^A[i] for i in range(N)])
for i in range(40):
    if (K >> i)&1 == 1:
        ans = max(ans,
                  sum(free[:i]) + L[i]*(2**i) + sum(default[i+1:]))
print(ans)

Solution (Python):
N, K = map(int, input().split())
num = list(map(int, input().split()))

now = 0
ans = 0
X = 0

list_10 = []

keta = 0
while(True):
  if 2**keta > K:
    
    break
  keta+=1

while(num != [0]*N):
  count_1 = 0
  count_0 = 0
  for i in range(N):
    if num[i] % 2 == 1:
      count_1 += 1
    else:
      count_0 += 1
    num[i] = num[i] // 2

  list_10.append([count_1, count_0])

  now += 1

if keta > len(list_10):
  for _ in range(keta-len(list_10)):
    list_10.append([0, N])

now = len(list_10)-1
for i in list_10[::-1]:
  if i[0] >= i[1]:
    ans += (2**now) * i[0]
  else:
    if X + 2**now > K:
      ans += (2**now) * i[0]
    else:
      ans += (2**now) * i[1]
      X += 2**now
  now-=1
  
print(ans)

Solution (Python):
N, K = map(int, input().split())
A = [int(s) for s in input().split()]


def cntbit(bit):
    cnt = 0
    for a in A:
        if a & bit:
            cnt += 1
    return cnt


def getans(bink):
    if len(bink) == 1:
        if bink == "0":
            return cntbit(1)
        else:
            return N - cntbit(1)

    ans = 0
    bit = 1 << (len(bink) - 1)
    if bink[0] == "0":
        return bit * cntbit(bit) + getans(bink[1:])
    else:
        ans1 = bit * (N - cntbit(bit)) + getans(bink[1:])
        ans2 = 0
        ans2 += bit * cntbit(bit)
        for i in range(len(bink) - 1):
            bit = 1 << i
            cnt = cntbit(bit)
            ans2 += bit * max(cnt, N - cnt)
        return max(ans1, ans2)


bink = bin(K)[2:]
bink = "0" * (40 - len(bink)) + bink
print(getans(bink))

Solution (Python):
import math
import sys

N, K = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))

def f(X):
    s = 0
    for a in A:
        s += X ^ a
    return s

def main():
    if K == 0:
        print(f(0))
        return

    max_f0, max_x0 = f(0), 0
    max_f1, max_x1 = max_f0, 0
    for i in range(int(math.log(K, 2)) + 1):
        if (max_x0 | (1 << i)) > K:
            break
        tmp = f(max_x0 | (1 << i))
        if tmp > max_f0:
            max_f0 = tmp
            max_x0 |= 1 << i

    for i in range(int(math.log(K, 2)), -1, -1):
        if (max_x1 | (1 << i)) > K:
            continue
        tmp = f(max_x1 | (1 << i))
        if tmp > max_f1:
            max_f1 = tmp
            max_x1 |= 1 << i

    print(max(max_f0, max_f1))


main()

Solution (Python):
import math
N, K = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
count = [0] * 40
if K == 0:
    print(sum(A))
    exit()
for a in A:
    for i in range(40):
        if a >> i & 1:
            count[i] += 1
ans = sum(count[_] * 2**_ for _ in range(int(math.log2(K)) + 1, 40))
while K:
    b = int(math.log2(K))
    if count[b] * 2 > N:
        
        ans += count[b] * 2**b
        K = 2**b - 1
    else:
        
        ans += (N - count[b]) * 2**b
        if K - 2**b:
            ans += sum(count[_] * 2**_
                       for _ in range(1 + int(math.log2(K - 2**b)), b))
        else:
            ans += sum(count[_] * 2**_ for _ in range(b))
        K -= 2**b
print(ans)

Solution (Python):
n, k = map(int, input().split())
vi = list(map(int, input().split()))
v = [0 for i in range(n)]
for i in range(n):
    v[i] = vi[i]

keta = 0
ki = k
while ki >= 1:
    ki /= 2
    keta += 1

x = [0 for i in range(keta)]
for h in range(keta):
    for i in range(n):
        if (v[i] % 2 == 1):
            x[h] += 1
        v[i] = v[i] // 2


ans = 0
for j in range(keta):
    i = keta - j - 1
    if (x[i] < n - x[i]) and (k >= 2 ** i):
        k -= 2 ** i
        ans += 2 ** i * (n-x[i])
        
    else:
        ans += 2 ** i * x[i]
        

ans += sum(v) * 2**keta
print(ans)

Solution (Python):






N, K = [int(i) for i in raw_input().strip().split(' ')]
A = [int(i) for i in raw_input().strip().split(' ')]


def f(x):
    s = 0
    for n in A:
        s += x ^ n
    return s


def main():
    mlist = [0]*40
    for a in A:
        astr = ('0'*40 + bin(a)[2:])[-40:]
        for i in range(40):
            ass = astr[i]
            if ass == '0':
                mlist[i] += 1
    
    cand = [0]*40
    for i in range(40):
        if mlist[i] > N/2:
            cand[i] = 1
    

    kbin = ('0'*40 + bin(K)[2:])[-40:]
    
    maxbin = ['0']*40
    for i in range(40):
        if kbin[i] == '0':
            continue
        if cand[i] == 1:
            maxbin[i] = '1'
        else:
            break
    i += 1
    while i < 40:
        maxbin[i] = str(cand[i])
        i += 1
    maxx = int(''.join(maxbin), 2)
    print f(maxx)


if __name__ == '__main__':
    main()

Solution (Python):
import functools
import math
n, k = map(int, input().split())
a = list(map(int, input().split()))

if k == 0:
    print(sum(a))
    exit()

bits = [0] * 50
for i in range(n):
    for j in range(50):
        if a[i] % 2:
            bits[j] += 1
        a[i] //= 2



@functools.lru_cache(maxsize=None)
def dfs(d, k):
    b = 2**d
    if k < b:
        return b * bits[d] + (dfs(d - 1, k) if d > 0 else 0)
    else:
        if d > 0:
            if b * 2 <= k:
                return dfs(d - 1, k - b) + max(b * bits[d], b * (n - bits[d]))
            else:
                return max(b * bits[d] + dfs(d - 1, k), b * (n - bits[d]) + dfs(d - 1, k - b))
        else:
            return max(b * bits[d], b * (n - bits[d]))


d = math.ceil(math.log2(k))
print(dfs(49, k))

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))

i = 1
while i <= K:
  i *= 2

x = 0
while i != 0:
  if sum([1 for a in A if a&i==0]) > N/2:
    if x+i <= K:
      x += i
  i //= 2;

print(sum([a^x for a in A]))

Solution (Python):


from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

N, K = map(int, raw_input().split())
A = map(int, raw_input().split())

cnt = [0] * 50

for p in A:
    hoge = p
    for i in range(50):
        cnt[i] += hoge % 2
        hoge /= 2

rec = [0] * 50
S = 0
for i in range(50):
    if N - cnt[i] < cnt[i]:
        S += cnt[i] * (2 ** i)
    else:
        S += (N - cnt[i]) * (2 ** i)
    rec[i] = S

rec = [0] + rec

ans = 0
S = 0
cur = 0

for i in range(50)[::-1]:
    if cur + (2 ** i) <= K:
        ans = max(ans, S + cnt[i] * (2 ** i) + rec[i])
        cur += (2 ** i)
        S += (N - cnt[i]) * (2 ** i)
    else:
        S += cnt[i] * (2 ** i)
ans = max(ans, S)

print ans

Solution (Python):
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from functools import lru_cache, reduce
from math import ceil, floor

import heapq
import itertools
import operator


def get_int():
    return int(input())


def get_str():
    return input().strip()


def get_int_list():
    return [int(i) for i in input().split()]


def get_char_list():
    return list(input().strip())


def bit1l(i):
    assert i > 0
    return len(bin(i)) - 3


def count1(i, xs):
    return sum(bool(i & x) for x in xs)


def main():
    n, k = get_int_list()
    xs = get_int_list()

    if k == 0:
        print(sum(xs))
        return
    gains = []
    for i in range(bit1l(k) + 1):
        gains.append((i, (len(xs) - count1(1 << i, xs) * 2) * (1 << i)))
    gains.sort(key=lambda x: x[1], reverse=True)
    best = 0
    for i, gain in gains:
        if gain < 0:
            break
        if k < best + (1 << i):
            continue
        best += (1 << i)
    print(sum((x ^ best) for x in xs))


if __name__ == '__main__':
    main()

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))

binary = [bin(a) for a in A]
bin_K = bin(K)
ma_len = max([len(e) for e in binary] + [len(bin_K)]) - 2
B = [e[2:].zfill(ma_len) for e in binary]
bin_K = bin_K[2:].zfill(ma_len)
ans = 0
X = []

flag = False
for i in range(ma_len):
    num_1 = 0
    num_0 = 0
    for j in range(N):
        if B[j][i] == "0":
            num_0 += 1
        else:
            num_1 += 1
    if num_1 >= num_0:
        added = "0"
        if bin_K[i] == "1":
            flag = True
    else:
        if flag:
            added = "1"
        else:
            if bin_K[i] == "1":
                added = "1"
            else:
                added = "0"
    if added == "1":
        ans += 2**(ma_len - i - 1) * num_0
    else:
        ans += 2**(ma_len - i - 1) * num_1
    

print(ans)

Solution (Python):
def inpl(): return [int(i) for i in input().split()]
N, K = inpl()
A = inpl()
H = [[0, 0] for _ in range(41)]
Kb = list(map(int, bin(K)[2:].zfill(41)))
for a in A:
    for i, v in enumerate(map(int, bin(a)[2:].zfill(41))):
        H[i][v] += 1 
ans = 0
ctr = 0
Hm = [max(j, k)*2**(40 - i) for i, [j, k] in enumerate(H)]
for i, v in enumerate(Kb):
    if not v:
        ctr += H[i][1]*2**(40-i)
    else:
        ans = max(ans, ctr + H[i][1]*2**(40-i) + sum(Hm[i+1:]))
        ctr += H[i][0]*2**(40-i)
print(max(ans, ctr))