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 = [ int(it) for it in input().split() ]
li = [ int(it) for it in input().split() ]

res_li = []
ma = max(max(li),K)
t = 1
K_li = []
k = K
K_haji = -1
for i in range(1000000):
  
  K_li.append(k%2)
  if (k%2==1):
    K_haji = i
  k//=2
  
  res_0 = 0
  res_1 = 0
  for v in li:
    res_0 += (v&t)
    res_1 += (v&t)^t
  res_li.append( (res_0,res_1)  )
  t*=2
  if (ma<t):
    break

smax = sum([ a for a,b in res_li ]) 
wlen = len(K_li)
smax = max(smax, sum([ res_li[it][K_li[it]] for it in range(wlen) ]) )
for i in range( wlen ):
  if ( K_li[i]==1 ):
    _sum = 0
    for j in range(wlen):
      if (i==j):
        _sum += res_li[j][0]
      elif (i<j):
        _sum += res_li[j][K_li[j]]
      elif (j<i):
        _sum += max(res_li[j])
    smax = max(smax, _sum)
print ( smax )

Solution (Python):
import numpy as np
N, K = map(int, input().split())
a = np.array(list(map(int, input().split())))
ans = 0
for i in range(50, -1, -1):
    s = np.sum((a >> i) & 1)
    if N - s > s:
        ans += 2 ** i
    if ans > K:
        ans -= 2 ** i
print(np.sum(ans ^ a))

Solution (Python):
n,k = map(int, input().split())
a = list(map(int, input().split()))
def d(n,k,a):
    b=[0]*41
    for i in a:
        for j in range(41):
            if (i>>j)&1==1:
                b[j] += 1
    return c(0,0,40,n,k,b)
def c(h,x,m,n,k,b):
    if m<0:
        return h
    g=(1<<m)
    y=x+g
    z=n-b[m]
    u=b[m]
    v=0
    w=0
    if u>z:
        v = c(h+g*u,x,m-1,n,k,b)   
    else:
        if y <= k:
            w = c(h+g*z,y,m-1,n,k,b)
        else:
            v = c(h+g*u,x,m-1,n,k,b)
    return max(v,w)
print(d(n,k,a))

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
l=max(len(bin(k)),len(bin(max(a))))-2
ans=0
for i in range(l,-1,-1):
  b=2**i
  m=sum([1 for j in a if j&b])
  if m<n-m and b<=k:
    m=n-m
    k-=b
  ans+=b*m
print(ans)

Solution (Python):
N, K = map(int,input().split())
As = list(map(int,input().split()))
bit_length = max(len(bin(K)), len(bin(max(As))))-2 
ans = 0
for i in range(bit_length,-1,-1): 
    bit = 2**i 
    
    n_bit = sum([1 for a in As if a & bit]) 
    
    
    if n_bit < N - n_bit and K-bit >= 0:
        n_bit = N - n_bit
        K -= bit
    ans += bit * n_bit
print(ans)

Solution (Python):
n,k=map(int,input().split())
a_list=list(map(int,input().split()))
count=[]
for i in range(40):
    count.append(0)
for i in a_list:
    temp=format(i,'040b')
    for j in range(40):
        if temp[j]=='1':
            count[j]=count[j]+1
ideal_l=[]
ideal=0
for i in range(40):
    if count[39-i]<n/2:
        ideal=ideal+(2**i)*(n-2*count[39-i])
    ideal_l.append(ideal)
ideal_l.reverse()
ideal_l.append(0)
bk=format(k,'040b')
def f(i):
    if i==40:
        return 0
    else:
        if bk[i]=='0':
            return f(i+1)
        else:
            if count[i]>=n/2:
                return ideal_l[i]
            else:
                a=ideal_l[i+1]
                b=(2**(39-i))*(n-2*count[i])+f(i+1)
                return max(a,b)
print(f(0)+sum(a_list))

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

k_candidates = []
for i in range(0, 40):
    x = len(A)
    y = 2 * len([a for a in A if a & (2 ** i) > 0])
    if x <= y:
        pass
    else:
        k_candidates.append(2**i)

k = 0
for i in reversed(k_candidates):
    if K >= k + i:
        k += i


def f(k):
    return sum([k ^ a for a in A])


print(f(k))

Solution (Python):
import math
N, K = map(int, input().split())
a = list(map(int, input().split()))
x = 0
if K == 0:
    x = 0
else:
    for i in range(41)[::-1]:
        cnt_1 = 0
        for _a in a:
            if _a & 2**i == 2**i:
                cnt_1 += 1
        if cnt_1 <= len(a)/2 and (x + 2**i) <= K:
            x += 2**i

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

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

max_A = max(A)
if max_A == 0:
  max_A_bin_len = 1
else:
  max_A_bin_len = len(bin(max_A)) - 2
  if K == 0:
    K_bin_len = 1
  else:
    K_bin_len = len(bin(K)) - 2
max_bin_len = max(max_A_bin_len, K_bin_len)
A_bin = [bin(a)[2:].zfill(max_bin_len) for a in A]
K_bin = bin(K)[2:].zfill(max_bin_len)

ans_cand1 = 0
ans_cand2 = 0
can_choose = 0
can_choose_forever = 0
calc_ans_cand2 = 0
start_calc_ans_cand2 = 0
for bit in range(max_bin_len):
  if not can_choose:
    if K_bin[bit] == '1':
      can_choose = 1
  A_one_num = 0
  for a in A_bin:
    if a[bit] == '1':
      A_one_num += 1
  if can_choose:
    if A_one_num < N-A_one_num:
      if not can_choose_forever:
        can_choose = 0
        if not calc_ans_cand2:
          ans_cand2 = ans_cand1 + (2**(max_bin_len-bit-1)) * A_one_num
          start_calc_ans_cand2 = 1
    else:
      can_choose_forever = 1
    ans_cand1 += (2**(max_bin_len-bit-1)) * (max(A_one_num, N-A_one_num))
  else:
    ans_cand1 += (2**(max_bin_len-bit-1)) * A_one_num
  if calc_ans_cand2:
    ans_cand2 += (2**(max_bin_len-bit-1)) * (max(A_one_num, N-A_one_num))
  if start_calc_ans_cand2:
    calc_ans_cand2 = 1
print(max(ans_cand1, ans_cand2))

Solution (Python):
def main():
    """
    1 <= N <= 10^5
    1 <= K <= 10^12
    1 <= Ai <= 10^12
    """
    N, K = map(int, input().split())
    *A, = map(int, input().split())

    ans4 = digit_dp(N, K, A)
    print(ans4)


def digit_dp(N, K, A):
    """桁DP

    http://drken1215.hatenablog.com/entry/2019/02/03/224200
    http://drken1215.hatenablog.com/entry/2019/02/04/013700
    https://qiita.com/nomikura/items/25883985ea148c3cf999
    """
    
    dp = [[0] * 2 for _ in range(100)]

    for i in range(100):
        dp[i][0] = dp[i][1] = -1

    dp[40][0] = 0
    for d in range(40-1, -1, -1):
        mask = 1 << d
        num = 0
        for a in A:
            if a & mask:
                num += 1

        if dp[d+1][1] >= 0:
            dp[d][1] = max(dp[d][1], dp[d+1][1] + mask * max(num, N-num))

        if dp[d+1][0] >= 0:
            if K & (1 << d):
                dp[d][1] = max(dp[d][1], dp[d+1][0] + mask * num)
                dp[d][0] = max(dp[d][0], dp[d+1][0] + mask * (N-num))
            else:
                dp[d][0] = max(dp[d][0], dp[d+1][0] + mask * num)

    ans = max(dp[0][0], dp[0][1])
    return ans


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    """
    1 <= N <= 10^5
    1 <= K <= 10^12
    1 <= Ai <= 10^12
    """
    N, K = map(int, input().split())
    *A, = map(int, input().split())

    ans = editorial(N, K, A)
    print(ans)


def editorial(N, K, A):
    """
    """
    ans = 0
    
    for d in range(40, -2, -1):
        
        
        if d != -1 and (K & (1 << d)) == 0:
            
            
            continue

        
        tmp = 0
        for e in range(40, -1, -1):
            mask = 1 << e

            
            num = 0
            for a in A:
                if a & mask:
                    num += 1

            if e > d:
                
                if K & mask:
                    tmp += mask * (N - num)
                else:
                    tmp += mask * num
            elif e == d:
                
                tmp += mask * num
            else:
                
                tmp += mask * max(num, N - num)

        ans = max(ans, tmp)

    return ans


if __name__ == '__main__':
    main()

Solution (Python):

import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, K: int, A: "List[int]"):
    bits = [0] * int(ceil(log(max(K, max(A))) / log(2)))
    for a in A:
        i = 0
        while 0 < (a >> i):
            bits[i] += (a >> i) & 1
            i += 1

    x = 0
    for i in range(len(bits)-1, -1, -1):
        c = bits[i]
        diff = (1 << i) if 2 * c <= N else 0
        if x + diff <= K:
            x += diff

    ret = 0
    for a in A:
        ret += x ^ a
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    K = int(next(tokens))  
    A = [ int(next(tokens)) for _ in range(N) ]  
    result = solve(N, K, A)
    print(result)

if __name__ == '__main__':
    main()

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


num = [0] * 41
for e in range(40, -1, -1):
    mask = 1 << e
    for a in A:
        if a & mask:
            num[e] += 1

res = 0
for d in range(40, -2, -1):
    
    
    if d != -1 and not (K & (1 << d)):
        continue

    tmp = 0
    for e in range(40, -1, -1):
        mask = 1 << e
        if e > d:
            if K & mask:
                tmp += mask * (N - num[e])
            else:
                tmp += mask * num[e]
        elif e == d:
            tmp += mask * num[e]
        else:
            tmp += mask * max(num[e], N - num[e])
    res = max(res, tmp)
print(res)

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

L = K+1
M = len(bin(L))-2
MM = max(M, len(bin(max(A)))-2)
best = []
ones_num = []
zeros_num = []
for m in range(MM):
    ones = sum([ (A[i]>>m)&1 for i in range(N) ])
    zeros = N - ones
    ones_num.append(ones)
    zeros_num.append(zeros)
    if ones >= zeros:
        best.append(0)
    else:
        best.append(1)
cur = sum([ (N-ones_num[m] if (best[m] and m < M-1) else ones_num[m])<<m for m in range(MM)])
ans = cur
m = M - 1
while m > 0:
    cur += (zeros_num[m]-ones_num[m])<<m
    m -= 1
    while (L >> m)&1 == 0:
        if best[m] == 1:
            cur += (ones_num[m]-zeros_num[m])<<m
        m -= 1
        if m < 0:
            break
    else:
        if best[m] == 1:
            cur += (ones_num[m]-zeros_num[m])<<m
        if cur > ans:
            ans = cur
print(ans)

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

c = [0]*40
for i in range(40):
	for a in A:
		c[i] += (a >> i) & 1

X = 0
ans = 0

for i in range(39, -1, -1):
	if c[i] < N-c[i] and X+(1<<i) <= K:
		X += (1<<i)
		ans += (N-c[i]) * (1<<i)
	else:
		ans += (c[i]) * (1<<i)

print(ans)

Solution (Python):
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
max_bit = 40
dp = [[-1] * 2 for i in range(41)]  

dp[0][0] = 0
for d in range(max_bit):
    mask = 1 << (max_bit-d-1)

    
    num = len([1 for i in range(N) if A[i] & mask])
    

    
    cost0 = mask * num
    cost1 = mask * (N - num)
    
    if dp[d][1] != -1:
        
        dp[d + 1][1] = max(dp[d + 1][1], dp[d][1] + max(cost0, cost1))

    
    if dp[d][0] != -1:
        if K & mask:  
            dp[d + 1][1] = max(dp[d + 1][1], dp[d][0] + cost0)

    
    if dp[d][0] != -1:
        if K & mask:
            dp[d + 1][0] = max(dp[d + 1][0], dp[d][0] + cost1)
        else:
            dp[d + 1][0] = max(dp[d + 1][0], dp[d][0] + cost0)


print(max(dp[max_bit][0], dp[max_bit][1]))

Solution (Python):
n,k = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
c,d,e,x,num = [0]*40,[0]*40,[0],[],0
def f(num,c):
    for j in range(40,-1,-1):
        if num>=2**j:
            c[j]+=1
            num-=2**j
for i in a: f(i,c)
f(k+1,d)
for i in range(40):
    if c[i]<=n//2: e.append(e[-1]+2**i)
    else: e.append(e[-1])
for i in range(39,-1,-1):
    if d[i]:
        m,m2,d2 = e[i]+num,0,[0]*40
        f(m,d2)
        for j in range(40): m2+=(2**j)*abs(n*d2[j]-c[j])
        x.append(m2)
        num+=2**i
if x: print(max(x))
else: print(sum(a))

Solution (Python):
nk = input().split()
n = int(nk[0])
k = int(nk[1])
alist = [int(a) for a in input().split()]


bit_count = [{0: 0, 1: 0} for i in range(42)]
for i in range(42):
    for a in alist:
        b = a >> i
        b &= 1
        which = 0 if b == 1 else 1
        bit_count[i][which] += 1


def calc_pow_multiple(digit, selected):
    count = bit_count[digit][selected]
    ret = 1<<digit
    ret *= count
    return ret


def calc_maxsum(kk, digit):
    if digit < 0:
        return 0
    if kk == (1<<(digit + 1)) - 1:
        partsum_0 = calc_pow_multiple(digit, 0)
        partsum_1 = calc_pow_multiple(digit, 1)
        return max(partsum_0, partsum_1) + calc_maxsum(kk>>1, digit - 1)

    kkbit = kk >> digit
    kkbit &= 1

    if kkbit == 0:
        return calc_pow_multiple(digit, 0) + calc_maxsum(kk, digit - 1)

    sum_0 = calc_pow_multiple(digit, 0) + calc_maxsum((1<<digit) - 1, digit - 1)
    sum_1 = calc_pow_multiple(digit, 1) + calc_maxsum(kk, digit - 1)
    return max(sum_0, sum_1)


print(calc_maxsum(k, 41))

Solution (Python):
nk = input().split()
n = int(nk[0])
k = int(nk[1])
alist = [int(a) for a in input().split()]


bit_count = [{0: 0, 1: 0} for i in range(42)]
for i in range(42):
    for a in alist:
        b = a >> i
        b &= 1
        which = 0 if b == 1 else 1
        bit_count[i][which] += 1


def calc_pow_multiple(digit, selected):
    count = bit_count[digit][selected]
    ret = 1<<digit
    ret *= count
    return ret


def calc_maxsum(kk, digit):
    if digit < 0:
        return 0
    if kk == (1<<(digit + 1)) - 1:
        partsum_0 = calc_pow_multiple(digit, 0)
        partsum_1 = calc_pow_multiple(digit, 1)
        return max(partsum_0, partsum_1) + calc_maxsum(kk>>1, digit - 1)

    kkbit = kk >> digit
    kkbit &= 1

    if kkbit == 0:
        return calc_pow_multiple(digit, 0) + calc_maxsum(kk, digit - 1)

    sum_0 = calc_pow_multiple(digit, 0) + calc_maxsum((1<<digit) - 1, digit - 1)
    sum_1 = calc_pow_multiple(digit, 1) + calc_maxsum(kk, digit - 1)
    return max(sum_0, sum_1)


print(calc_maxsum(k, 41))

Solution (Python):
import numpy as np

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

digit = len(bin(max(A+[K])))-2  

binA = np.array([list(bin(a)[2:].rjust(digit, '0')) for a in A]).astype(int)
d_sum = binA.sum(axis=0)  
max_size = binA.shape[0]


def max_sum(u_sum, d):
    if K-u_sum >= 2**(digit-1-d):
        if d == digit-1:
            return get_free_sum([d_sum[-1]], max_size)
        else:
            return max(max_sum(u_sum+2**(digit-1-d), d+1)+(max_size-d_sum[d])*2**(digit-1-d),
                       get_free_sum(d_sum[d+1:], max_size)+d_sum[d]*2**(digit-1-d))
    else:
        if d == digit-1:
            return d_sum[-1]
        else:
            return max_sum(u_sum, d+1)+d_sum[d]*2**(digit-1-d)


def get_free_sum(ones_list, nums):
    return sum([max(ones, nums-ones)*2**i for i, ones in enumerate(ones_list[::-1])])


print(max_sum(0, 0))

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

X = 0
ans = 0
for i in range(40, -1, -1):
    bit = 1 << i
    count = 0
    for a in A:
        if bit & a:
            count += 1
    if N >= count * 2 and (X^bit) <= K:
        X ^= bit
        count = N - count
    ans += count * bit

print(ans)

Solution (Python):
N,K=map(int, input().split())
a=list(map(int, input().split()))
x=0
len_bin=len(bin(K))-2

def bin_l(n,i):
    return (n>>(len_bin-i-1))%2

for i in range(len_bin):
    zero=0
    one=0
    for j in range(N):
        if bin_l(a[j],i)==0:
            zero+=1
        else:
            one+=1
    x=x<<1
    if zero>one and x<(K>>(len_bin-i-1)):
        x+=1

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

Solution (Python):
N, K = map(int, input().split())
A=list(map(int, input().split()))
L=[0 for _ in range(40)]
ans=[]
ans.append(sum(a^K for a in A))
for a in A:
    i=0
    while a:
        if a&1==1:
            L[i]+=1
        a=a>>1
        i+=1

opt_str=''
for l in L[::-1]:
    if l > N-l:
        opt_str+='0'
    else:
        opt_str+='1'
opt=int(opt_str,2)

for i in range(40):
    if ((K>>i)&1)==1:
        Kr=(K&((((1<< 40-i)-1)<<(i+1))))|(opt&(1 << i)-1)
        ans.append(sum(a ^ Kr for a in A))

print(max(ans))

Solution (Python):
N, K = map(int, input().split())
A=list(map(int, input().split()))
L=[0 for _ in range(40)]
ans=[]
ans.append(sum(a^K for a in A))
for a in A:
    i=0
    while a:
        if a&1==1:
            L[i]+=1
        a=a>>1
        i+=1

opt_str=''
for l in L[::-1]:
    if l > N-l:
        opt_str+='0'
    else:
        opt_str+='1'
opt=int(opt_str,2)

for i in range(40):
    tmp=0
    if ((K>>i)&1)==1:
        Kr=(K&((((1<< 40-i)-1)<<(i+1))))|(opt&(1 << i)-1)
        ans.append(sum(a ^ Kr for a in A))

print(max(ans))

Solution (Python):
N, K = map(int, input().split())
A=list(map(int, input().split()))
L=[0 for _ in range(40)]
ans=[]
ans.append(sum(a^K for a in A))
for a in A:
    i=0
    while a:
        if a&1==1:
            L[i]+=1
        a=a>>1
        i+=1

opt_str=''
for l in L[::-1]:
    if l > N-l:
        opt_str+='0'
    else:
        opt_str+='1'
opt=int(opt_str,2)

for i in range(40):
    Kr=(K&((((1<< 40-i)-1)<<(i+1))))|(opt&(1 << i)-1)
    if Kr<=K:
        ans.append(sum(a ^ Kr for a in A))

print(max(ans))

Solution (Python):
import numpy as np
N,K = list(map(int,input().split()))
A1 = list(map(int,input().split()))
A = list(map(lambda x:format(x,'050b'),A1))
K1 = format(K,"050b")
count = [0]*50
count = np.array(count)
ans = ["0"]*50
for a in A:
    count += np.array(list(map(int,list(str(a)))))
small_flag = 0
H = N/2
for a in range(50):
    if small_flag !=0:
        if count[a]>H:
            ans[a]="0"
        else:
            ans[a]="1"
    else:
        if count[a]<H and K1[a]=="1":
            ans[a]="1"
        elif count[a]>=H and K1[a]=="1":
            small_flag = "1"
ans = int("".join(ans),2)
ans1 = 0
for i in A1:
    ans1 += i^ans
print(ans1)

Solution (Python):

import sys

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

keta=0

for i in range(50,-1,-1):
	if (K>>i)&1:
		keta=i+1
		break



C=[ 0 for i in range(keta) ]	


for a in A:
	for k in range(keta-1,-1,-1):
		
		if (a>>k)&1:		
			C[k]+=1



X=0	


len_c=len(C)

for i in range(len_c-1,-1,-1):
	ci=C[i]
	if  C[i]<(N+1)/2:
		if X+2**i<=K:
			X+=2**i		
					

ans=0
for a in A:
	ans+=X^a

print ans

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
ma=max(A)
ma=max(ma,K)
num=len(bin(ma)[2:])
B=[]
count=[0]*num
for a in A:
    b=bin(a)[2:].zfill(num)
    B.append(b)
    for i in range(num):
        if b[i]=="0":
            count[i]-=1
        else:
            count[i]+=1
s=""
for i in count:
    if i<0:
        s+="1"
    else:
        s+="0"
k=bin(K)[2:].zfill(num)
t=""
for i in range(num):
    if s[i]<k[i]:
        t+=s[i:]
        break
    else:
        t+=k[i]
t=int(t,2)
sum=0
for i in A:
    sum+=i^t
print(sum)

Solution (Python):
from sys import exit
N,K = [int(n) for n in input().split()]
A = [int(n) for n in input().split()]







sums = []
maximum_size = len(bin(max(A))) - 2
countdic = [{"0":0,"1":0} for _ in range(maximum_size)]
for i in range(N):
    
    ta = bin(A[i])[2:].zfill(maximum_size)
    ta = ta[::-1]
    
    
    for i in range(len(ta)):
        if ta[i] == "0":
            countdic[i]["0"] +=1
        else:
            countdic[i]["1"] +=1

ans = ""
for num in countdic:
    if num["0"] < num["1"]:
        ans = "0" + ans
    else:
        ans = "1" + ans
lim = bin(K)[2:]

if K != 0:
    maxcand_size = len(bin(K)) - 2
    
    ans = abs(maxcand_size - len(ans))*"1" + ans
    ans = ans[-maxcand_size:]
    
    
    if(int(ans,2) > K):
        for i in range(1,len(lim)):
            if(lim[i] == "0" and ans[i] == "1"):
                ans = ans[:i] + "0" + ans[i+1:]
                if(int(ans,2) <= K):break
    
else:
    ans = "0"





ans = int(ans,2)
answer = 0

for i in range(N):
    answer+=ans^A[i]
print(answer)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
bits = [0 for i in range(41)]
for i in range(N):
    for j in range(41):
        if A[i] & (1 << j):
            bits[40-j] += 1

bin_K = '0' * (43 - len(bin(K))) + bin(K)[2:]
x = 0
flag = 0
threshold = N // 2 + 1
for i in range(41):
    if flag == 1:
        if bits[i] < threshold:
            x += 1 << (40-i)
    elif flag == 0:
        if bits[i] < threshold and bin_K[i] == '1':
            x += 1 << (40-i)
        elif bits[i] >= threshold and bin_K[i] == '1':
            flag = 1

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

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
bits = [0]*41
for i in range(N):
    for j in range(41):
        if A[i] & (1 << j):
            bits[40-j] += 1


bin_K = '0' * (43 - len(bin(K))) + bin(K)[2:]
x = 0
flag = 0  
threshold = N // 2 + 1
for i in range(41):
    if flag == 1:
        if bits[i] < threshold:
            x += 1 << (40-i)
    elif flag == 0:
        if bits[i] < threshold and bin_K[i] == '1':
            x += 1 << (40-i)
        elif bits[i] >= threshold and bin_K[i] == '1':
            flag = 1


ans = 0
for i in range(N):
    ans += x ^ A[i]

print(ans)

Solution (Python):

n,k=map(int,input().split())
a=list(map(int,input().split()))
bits=list(bin(k+1)[2:])
bits=list(map(int,bits))
stack=[0]*40
ans=0

for i in a:
  num=bin(i)[2:]
  for j in range(len(num)):
    if num[j]=="1":
      stack[len(num)-j-1]+=1


for i in range(len(bits)):
  possible_ans=[q for q in bits]
  ans_stack=0
  
  
  if possible_ans[i]==0:
    continue
  possible_ans[i]=0
  
  
  for j in range(40):
    if j<len(bits)-i-1:
      ans_stack+=max(stack[j]*2**j,(n-stack[j])*2**j)
    elif j<len(bits) and possible_ans[len(bits)-j-1]==1:
      ans_stack+=(n-stack[j])*2**j
    else:
      ans_stack+=stack[j]*2**j
  ans=max(ans,ans_stack)

print(ans)

Solution (Python):
def solve(string):
    n, k, *a = map(int, string.split())
    x = 0
    p = 2**(len("{:b}".format(k)) - 1)
    while p > 0:
        if sum([1 for _a in a if p & _a]) < n / 2 and x + p <= k:
            x += p
        p //= 2
    return str(sum([x ^ _a for _a in a]))


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))

Solution (Python):
def solve(string):
    n, k, *a = map(int, string.split())
    if k == 0:
        x = 0
    else:
        l = len("{:b}".format(k))
        base = [2**(l - i - 1) for i in range(l)]
        count = [0] * l
        for _a in a:
            tmp = "{:b}".format(_a)
            for i, _f in enumerate(tmp[::-1]):
                if i >= l:
                    break
                if _f == "1":
                    count[l - i - 1] += 1
        x = 0
        for _c, _b in zip(count, base):
            if _c < n / 2 and x + _b <= k:
                x += _b
    return str(sum([x ^ _a for _a in a]))


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))

Solution (Python):
def solve(n, k, a):
    x = [2**i for i in range(50, -1, -1)]
    ans = 0
    for x_i in x:
        u, v = 0, 0
        for a_j in a:
            u += x_i ^ (x_i & a_j)
            v +=       (x_i & a_j)
        if (x_i <= k) and (u > v):
            k -= x_i
            ans += u
        else:
            ans += v
    return ans

assert solve(3, 7, [1,6,3]) == 14
assert solve(4, 9, [7,4,0,3]) == 46

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

Solution (Python):

def get_input():
    N,K = map(int,input().split())
    A = map(int,input().split())
    return N,K,A

def solve(N,K,A):
    sum_per_digit_list = sum_digit(A)
    K_b = to_2digit(K+1)
    cand = []
    for i in range(40):
        if K_b[i] ==1:
            cand.append(calc_opt(i,K_b,sum_per_digit_list,N))
    return max(cand)

def calc_opt(i,K_b,sum_per_digit_list,N):
    opt = 0
    for j in range(40):
        if j < i :
            opt+= max(N-sum_per_digit_list[j], sum_per_digit_list[j]) * 2**j
        elif j==i:
            opt+= sum_per_digit_list[j] * 2**j

        else:
            if K_b[j] == 1:
                opt+= (N - sum_per_digit_list[j]) * 2**j
            else:
                opt+= sum_per_digit_list[j] * 2**j
    return opt



def sum_digit(A):
    sum_per_digit_list = []
    numbers = list(A)
    for i in range(40):
        sum_per_digit_list.append(sum([number %2 for number in numbers]))
        numbers = [number //2 for number in numbers]
    return sum_per_digit_list
    
def to_2digit(number):
    digits = []
    for i in range(40):
        digits.append(number %2)
        number = number //2 
    return digits


if __name__ == "__main__":
    N,K,A = get_input()
    print(solve(N,K,A))

Solution (Python):
import math

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


bit_num = math.floor(math.log2(max(max(a),k)))+1


num_one = []
for i in range(bit_num):
  
  num_one_tmp = 0
  for j in a:
    num_one_tmp += (j >> i) & 1
  num_one.append(num_one_tmp)

  
if k == 0:
  bit_k = 1
else:
  bit_k = math.floor(math.log2(k))+1









constant_ans = 0
for i in range(bit_k,bit_num):
  constant_ans += num_one[i] * 2**i

ans = 0


for i in range(bit_k)[::-1]:
  
  
  if 2**i > k:
    constant_ans += num_one[i] * 2**i
  
  
  else:
    
    variant_ans = num_one[i] * 2**i
    
    for j in range(i):
      
      if num_one[j] >= (n+1)//2:
        variant_ans += num_one[j] * 2**j
      
      else:
        variant_ans += (n-num_one[j]) * 2**j
    ans = max(ans,constant_ans+variant_ans)

    
    constant_ans += (n-num_one[i]) * 2**i
    k -= 2**i
  
  
  
ans = max(ans,constant_ans)
print(ans)

Solution (Python):
N, k = map(int, input().split())
d = {i: 0 for i in range(40)}
for n in map(int, input().split()):
    for j in range(40):
        if (n >> j) & 1:
            d[j] += 1
ans = 0
num = 0
for i in range(39, -1, -1):
    if num + 2 ** i <= k:
        if N - 2 * d[i] < 0:
            ans += 2 ** i * d[i]
        else:
            ans += 2 ** i * (N - d[i])
            num += 2 ** i
    else:
        ans += 2 ** i * d[i]
print(ans)

Solution (Python):




N , K = map(int, input().split())
an = list(map(int,input().split()))
lenbitK = len(bin(K)) - 2
lenmax = max(len(bin(max(an))) - 2,lenbitK)
usebitK = [0] * lenmax
anbit = [0] * lenmax
for a in an:
    for i in range(len(bin(a))-2):
        if a>>i & 1 :
            anbit[i] += 1
tempK = 0
for i in reversed(range(lenbitK)):
    if (anbit[i] < ((N>>1)+(N&1)) ) and (tempK + (1<<i)  <= K) :
        usebitK[i] = 1
        tempK += (1<<i)
ans = 0


for j in range(lenmax):
    if usebitK[j] == 0:
        ans += anbit[j] * (1<<j)
    else:
        ans += (N - anbit[j]) * (1<<j)
print(ans)

Solution (Python):
N,K=map(int,input().split())
A=[int(i) for i in input().split()]
ans=0
for i in range(40,-1,-1):
    bit=0
    for a in A:
        bit+=((a>>i)&1)
    cond=2**i
    if (N-bit)>bit and K>=cond:
        ans+=(N-bit)*cond
        K-=cond
    else:
        ans+=bit*cond
print(ans)

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
tp=[0]*121
for a in A:
    index=0
    while a!=0:
        tp[index]+=a%2
        a//=2
        index+=1
L=[i for i in range(len(tp)) if tp[i] <= N//2][::-1]
x = 0
for i in L:
    if x + 2**i <= K:
        x+=2**i
print(sum([x^i for i in A]))

Solution (Python):
from functools import lru_cache


def get_bit(n, d):
    return (n >> d) & 1


@lru_cache(maxsize=None)
def xor(bit, digit):
    """
    A の各要素について右から digit 桁目を bit で XOR した合計
    :param int bit:
    :param int digit:
    :return:
    """
    assert bit in [0, 1]
    
    
    
    if bit == 0:
        return bit_counts[digit] << digit
    else:
        return (N - bit_counts[digit]) << digit


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

DIGIT = 50
bit_counts = [sum([get_bit(a, d=d) for a in A]) for d in range(DIGIT)]


dp = [[-float('inf') for _ in range(2)] for _ in range(DIGIT + 1)]



dp[-1][0] = 0
for d in reversed(range(DIGIT)):
    k = get_bit(K, d=d)
    
    dp[d][0] = max(dp[d][0], dp[d + 1][0] + xor(bit=k, digit=d))
    
    if k == 1:
        dp[d][1] = max(dp[d][1], dp[d + 1][0] + xor(bit=0, digit=d))
    
    dp[d][1] = max(dp[d][1], dp[d + 1][1] + xor(bit=0, digit=d))
    dp[d][1] = max(dp[d][1], dp[d + 1][1] + xor(bit=1, digit=d))

print(max(dp[0]))

Solution (Python):
num_terms, max_value = map(int, input().split())
coef = [int(a) for a in input().split()]

res = 0
for i in range(40, -1, -1):
    num_bits = 0
    for a in coef:
        num_bits += ((a >> i) & 1)
    cand = 2**i
    if (num_terms-num_bits) > num_bits and cand <= max_value:
        res += (num_terms - num_bits)*cand
        max_value -= cand
    else:
        res += num_bits*cand

print(res)

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

ans = 0
for i in range(40, -1, -1):
    j = 2 ** i
    count = len([1 for temp in a if temp&j > 0])
    if count < n - count and j <= k:
        k -= j
        count = n - count
    ans += j * count
print(ans)

Solution (Python):
N,K = map(int,input().split())
A = list(map(int,input().split()))
max_bit = 40
ans = 0
for i in range(max_bit,-1,-1):
    bit = 2**i 
    c = len([1 for j in A if j&bit > 0]) 
    if 2*c < N and bit <= K:
        c = N-c
        K -= bit
    ans += bit*c
print(ans)

Solution (Python):
import math
def getInt(): return int(input())
def getIntList(): return [int(x) for x in input().split()]
def zeros(n): return [0]*n
class Debug():
    def __init__(self):
        self.debug = True
 
    def off(self):
        self.debug = False
 
    def dmp(self, x, cmt=''):
        if self.debug:
            if cmt != '':
                w = cmt + ': ' + str(x)
            else:
                w = str(x)
            print(w)
        return x
def prob(): 
    d = Debug()
    d.off()
    N, K = getIntList()
    d.dmp((N, K), 'N, K')
    A = getIntList()
    d.dmp((A), 'A')
    if K == 0:
        x = 0
    else:
        lg = int(math.log2(K))
        mask = 1 << lg
        x = 0
        d.dmp(x,'x')
        lessK = False  
        while mask > 0:
            cz, co = 0, 0
            for i in range(N):
                if A[i] & mask == 0:
                    cz += 1
                else:
                    co += 1
            if cz > co:
                if K & mask or lessK:
                    x += mask
            if (x & mask == 0) and mask & K:
                lessK = True
            mask >>= 1
            d.dmp((mask,x),'mask,x')
    d.dmp((x),'x')
    ans = 0
    for i in range(N):
        d.dmp((x ^ A[i]),'x ^ A[i]')
        ans += x ^ A[i]
    return ans


ans = prob()
print(ans)

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

memo = [0 for i in range(65)]
AA = [i for i in A]
for i in AA:
	r = 0
	while i > 0:
		if((i & 1) == 1):
			memo[r] = memo[r] + 1
		i = i // 2
		r = r + 1
res = 0
for i in range(50):
	if 2*memo[i] < N:
		res = res + (1 << i)
d = 51
while res > K:
	if ((res >> d) & 1) == 1 and ((K >> d) & 1) == 0:
		res = res ^ (1 << d)
	d = d - 1
    
ans = 0
for i in A:
	ans = ans + (res ^ i)
print(ans)