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):
def xxor(N: int, K: int, A: list) -> int:
    opt = 0
    num_digit_2 = 0  
    while 2 ** num_digit_2 < K:
        num_digit_2 += 1

    
    mask = 1
    for _ in range(num_digit_2):
        count_0, count_1 = 0, 0
        for a in A:
            if a & mask > 0:
                count_1 += 1
            else:
                count_0 += 1

        if count_0 > count_1:
            opt = opt | mask

        mask <<= 1

    
    max_ret = 0
    x = opt
    
    
    for i in range(40):
        mask = 1 << (40 - i - 1)

        if x < K + 1:
            temp = sum(a ^ x for a in A)
            max_ret = max(temp, max_ret)

        x2 = (x & ~mask)  
        if x2 < K + 1:
            temp = sum(a ^ x2 for a in A)
            max_ret = max(temp, max_ret)

        x = ((K + 1) & ~(mask - 1)) | (opt & (mask - 1))

    return max_ret


if __name__ == "__main__":
    N, K = [int(s) for s in input().split()]
    A = [int(s) for s in input().split()]

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

Solution (Python):
from math import log2

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

def f(n):
    return sum(n^i for i in A)

K += 1

if K == 1:
    print(f(0))
else:
    mb = int(log2(K))
    hN = N / 2

    s = 0
    A_ = A.copy()
    for i in range(mb+1):
        s += (0 if sum(i &0x01 for i in A_) >= hN else 1) * (1 << i)
        A_ = [i >> 1 for i in A_]

    if s >= K:
        def g(i, n, k):
            mask = (2**i) - 1
            s_ = (s & mask) | (k - (k & mask))
            s_ -= (s_ & (1 << i))
            return s_

        gl = [g(i, s, K) for i, b in enumerate("{:b}".format(K)[::-1]) if b == "1"]
        fl = [f(i) for i in gl]
        print(max(fl))
    else:
        print(f(s))

Solution (Python):

from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007


"""
t,x = LI()
print(t/x)
"""


"""
n= II()
a = LI()
m = max(a)
if m >= sum(a)-m:
    print("No")
else:
    print("Yes")
"""


"""
n,m = LI()
x = LI()
x.sort()
l = [x[i+1]-x[i] for i in range(m-1)]
l.sort()
l = l[::-1]
ans = sum(l[max(n-1,0):])
print(ans)
"""


n,k = LI()
a = LI()
k = list(map(int,list(bin(k)[2:])))
l = len(k)
for i in range(n):
    a[i] = list(map(int,list(bin(a[i])[2:])))
    l = max(l,len(a[i]))
for i in range(n):
    for j in range(l-len(a[i])):
        a[i].insert(0,0)
for j in range(l-len(k)):
    k.insert(0,0)
s = [[0,0] for i in range(l)]
pow2 = [1 for i in range(l)]
for i in range(l-1)[::-1]:
    pow2[i] = pow2[i+1]*2
for i in a:
    for j in range(l):
        s[j][0] += pow2[j]*i[j]
        s[j][1] += pow2[j]*(not i[j])
dp = [0 for i in range(l+1)]
small = False
for i in range(l):
    if not small:
        if not k[i]:
            dp[i+1] += dp[i]+s[i][0]
        else:
            if s[i][0] >= s[i][1]:
                dp[i+1] += dp[i]+s[i][0]
                small = True
            else:
                dp[i+1] += dp[i]+s[i][1]
    else:
        dp[i+1] += dp[i]+max(s[i])
print(dp[l])

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

ans = 0
for d in range(40, -1, -1):
    x = 1<<d
    n_bin = len([1 for i in range(n) if a[i]&x > 0])
    if n_bin < n-n_bin and x <= k: 
        n_bin = n - n_bin 
        k -= x 
    ans += x*n_bin

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

def xxor(X):
    ans = 0
    for A in A_arr:
        ans += X ^ A
    return ans

mi_arr = [0]*40
xxor_0 = xxor(0)
for i in range(40):
    x = 1 << i
    if xxor_0 < xxor(x):
        mi_arr[i] = 1

x_max = xxor(K)
K_i_max = [0]*40
for i in range(40):
    K_i = (K >> i) % 2
    if K_i == 0:
        continue

    mi_k_arr = [x for x in mi_arr]
    mi_k_arr[i] = 0
    for j in range(i+1, 40):
        K_j = (K >> j) % 2
        mi_k_arr[j] = K_j
    xi_max = 0
    for i in reversed(range(40)):
        xi_max = xi_max << 1
        xi_max += mi_k_arr[i]

    x_max = max(x_max, xxor(xi_max))

print(x_max)

Solution (Python):
def run(N, K, A):
    '''
    K <= 10^12 ~= 2^40
    Kの2進数における各桁ごとの最大となるKを求めることができる(O(logK))
    Kの2進数における最初の1を0に変える位置をk_nとする
    最初に変える位置の前はすべてKと同じ、それ以降は最大を取るものを選択する(O(log(K)))
    k_nが0の場合は、全て同じパターンとしてスキップする
    上記の最大のものを習得する
    '''
    cnt1 = []

    
    k_n = len(bin(K)) - 2

    
    max_a = len(bin(max(A))) - 2
    max_a = max(max_a, k_n)

    
    K_bit = '{:b}'.format(K).zfill(max_a)
    A_bit = []
    for i in range(len(A)):
        A_bit.append('{:b}'.format(A[i]).zfill(max_a))

    
    bit_v = []
    for i in range(max_a):
        bit_v.append(2**(max_a-i-1))

    
    for j in range(max_a):
        cnt = 0
        for i in range(N):
            if A_bit[i][j] == '1':
                cnt += 1
        cnt1.append(cnt)

    
    
    ret = 1
    for i in range(k_n+1):
        tmp1 = 0
        max_flg = False
        for j in range(max_a):
            if max_a - j == k_n - i:  
                
                tmp1 += bit_v[j] * cnt1[j]
                
                if K_bit[j] == '1':
                    max_flg = True
            elif not max_flg:  
                
                tmp1 += bit_v[j] * (cnt1[j]**(1-int(K_bit[j]))) * ((N-cnt1[j])**(int(K_bit[j])))
            else:  
                tmp1 += bit_v[j] * max(cnt1[j], N - cnt1[j])
        ret = max(ret, tmp1)
    return ret


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    print(run(N, K, A))


if __name__ == '__main__':
    main()

Solution (Python):












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

ck = [0 for i in range(40)]
for i in a:
    for j in range(40):
        if i>>j & 1:
            ck[j] += 1

fx = []
for i in range(40):

    if (k+1)>>i & 1 == 0:
        continue

    ans = 0
    for j in range(40):
        if j > i:
            if ((k+1)>>j) & 1:
                ans += (1<<j) * (n-ck[j])
            else:
                ans += (1<<j) * ck[j]
        elif j == i:
            ans += (1<<j) * ck[j]
        else:
            if ck[j] * 2 > n:
                ans += (1<<j) * ck[j]
            else:
                ans += (1<<j) * (n-ck[j])

    fx.append(ans)

print(max(fx))

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

fmax = 0
for i in range(40, 0, -1):
  x = 2 ** (i - 1)
  f1 = 0
  f0 = 0
  for a in A:
    a_ = a & x
    f1 += x ^ a_
    f0 += a_
  
  if f0 >= f1:
    fmax += f0
  else:
    if k >= x:
      fmax += f1
      k -= x
    else:
      fmax += f0
print(fmax)

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

fmax = 0
for i in range(40, 0, -1):
  x = 2 ** (i - 1)
  f1 = 0
  f0 = 0
  for a in A:
    a_ = a & x
    f1 += x ^ a_
    f0 += a_
  
  if f0 >= f1:
    fmax += f0
  else:
    if k >= x:
      fmax += f1
      k -= x
    else:
      fmax += f0
print(fmax)

Solution (Python):
N, K = map(int,input().split(" "))
A = list(map(int,input().split(" ")))
A_ = [0] * N

k = K
K_dig = -1
while k > 0:
    k >>= 1
    K_dig += 1

border = ((1 << (K_dig+1)) - 1)
for i in range(N):
    if A[i] > border:
        a = A[i]
        j = (K_dig + 1)
        while a > border:
            if (a >> j) & 1:
                a -= (1 << j)
            j += 1
        A_[i] = a
    else:
        A_[i] = A[i]


def dfs(dig,curValue):
    if dig == -1:
        return curValue
    if (curValue + (1 << dig)) > K:
        return dfs(dig-1,curValue)

    oneCount = 0
    for i in range(N):
        if (A_[i] >> dig) & 1:
            oneCount += 1
    if oneCount <= (N-oneCount):
        return dfs(dig-1,curValue + (1 << dig))
    else:
        return dfs(dig-1,curValue)
    
val = dfs(K_dig,0)

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

Solution (Python):
n,k = list(map(int, input().split()))
a=list(map(int, input().split()))
x=0
ans = 0
for i in range(45,-1,-1):
  c=0
  for p in a:
    if (p >> i) & 1:
      c += 1
  if n - c > c and x + (1<<i) <= k:
    ans += (n-c) * (1<<i)
    x += 1<<i
  else:
    ans += c * (1<<i)
print(ans)

Solution (Python):
from math import log2
import sys
N, K = [int(x) for x in input().split()]
a = [int(y) for y in input().split()]


def nketame(a, n):
    return (a & (1 << n)) >> n


def f(x):
    return sum([y ^ x for y in a])


if K == 0:
    print(f(0))
else:
    ans = []
    b = 0
    for i in range(int(log2(K))+1, 0, -1):
        
        c = [nketame(x, i-1) for x in a].count(1)
        if c < N-c:
            bb = b + (1 << (i-1))
        else:
            bb = b
        if bb <= K:
            b = bb
            ans.append(b)
    
    print(f(max(ans)))

Solution (Python):
N, K = map(long, raw_input().split())
A = map(long, raw_input().split())
p = 45
X = 0
while p >= 0:
  mask = 2 ** p
  count0 = sum([0 if mask & a > 0 else 1 for a in A])
  count1 = N - count0
  if X+mask <= K and count1 < count0:
    X += mask
  p -= 1
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()))

s = [0 for _ in range(50)]



dp = [[0 for _ in range(2)] for _ in range(50)]


for aa in a:
    for j in range(50):
        if (aa >> j) & 1:
            s[j] += 1

for j in sorted(range(45 + 1), reverse=True):
    if (K >> j) & 1:
        
        
        dp[j][0] = dp[j + 1][0] + ((N - s[j]) << j)
        if dp[j + 1][1] == 0:
            dp[j][1] = dp[j + 1][0] + (s[j] << j) 
        else:
            dp[j][1] = max(
                dp[j + 1][1] + (s[j] << j),
                dp[j + 1][1] + ((N - s[j]) << j),
                dp[j + 1][0] + (s[j] << j)
            )
    else:
        
        
        dp[j][0] = dp[j + 1][0] + (s[j] << j)
        if dp[j + 1][1] == 0:
            dp[j][1] = 0 
        else:
            dp[j][1] = max(
                dp[j + 1][1] + (s[j] << j),
                dp[j + 1][1] + ((N - s[j]) << j)
            )
print(max(dp[0][0], dp[0][1]))

Solution (Python):
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    EXP_MAX = 41
    cnt = [0] * (EXP_MAX+1)
    for a in A:
        for i in range(EXP_MAX+1):
            cnt[i] += a//(2**i) % 2
    tmp = 0
    ans = 0
    for i in range(EXP_MAX, -1, -1):
        if cnt[i] * 2 < N and tmp + 2**i <= K:
            tmp += 2**i
            ans += 2**i * (N - cnt[i])
        else:
            ans += 2**i * cnt[i]
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
N, K = map(int, input().split())
bitK = format(K, "b").zfill(41)
A = [int(a) for a in input().split()]
DP = [[0, 0] for _ in range(41)] 
Ones = [0] * 41
for a in A:
    bita = format(a, "b").zfill(41)
    for i in range(41):
        Ones[i] += int(bita[i])

if bitK[0] == "1":
    DP[0][0] = (2 ** 40) * (N - Ones[0])
    DP[0][1] = (2 ** 40) * Ones[0]
else:
    DP[0][0] = (2 ** 40) * Ones[0]
    DP[0][1] = 0

for i in range(1, 41):
    oneNum = Ones[i]
    digit = 2**(40-i)
    if bitK[i] == "1":
        DP[i][0] = DP[i-1][0] + digit * (N - oneNum)
        DP[i][1] = DP[i-1][0] + digit*oneNum
        if DP[i-1][1] > 0:
            DP[i][1] = max(DP[i][1], DP[i-1][1] + digit*max(oneNum, N-oneNum))
    else:
        DP[i][0] = DP[i-1][0] + digit*oneNum
        if DP[i-1][1] > 0:
            DP[i][1] = DP[i-1][1] + digit*max(oneNum, N-oneNum)

print(max(DP[-1]))

Solution (Python):
import operator

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

k = [((K+1)&(1<<i))>>i for i in range(40)]

m = [0]*40
for i in range(40):
	c = sum([(a&(1<<i))>>i for a in A])
	m[i] = 0 if N<2*c else 1

f = 0
b = [1<<i for i in range(40)]
for i in range(40):
	if k[i]==1:
		x = sum(map(operator.mul, m[:i]+[0]+k[i+1:], b))
		f = max(f, sum([x^a for a in A]))

print(f)

Solution (Python):
import operator

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

k = [((K+1)&(1<<i))>>i for i in range(40)]

m = [0]*40
for i in range(40):
	c = 0
	for a in A:
		c += (a&(1<<i))>>i
	
	if N < 2*c:
		m[i] = 0
	else:
		m[i] = 1

f = 0
b = [1<<i for i in range(40)]
for i in range(40):
	if k[i]==1:
		x = sum(map(operator.mul, m[:i]+[0]+k[i+1:], b))
		f = max(f, sum([x^a for a in A]))

print(f)

Solution (Python):
ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))


N,K=rl()
A=rl()

digit = len(format(max(max(A),K),'b'))+1
cnt = [[0,0] for _ in range(digit)]
for i in range(digit):
    for a in A:
        cnt[i][a>>(digit-1-i) & 1] += 1

dp = [[-1,-1] for _ in range(digit)]
dp[0][0]=0





from itertools import product

for i, less in product(range(digit-1),(0,1)):
    if dp[i][less] == -1: continue
    
    max_d = less or K>>(digit-1-i-1)&1
    
    for d in range(max_d+1):
        
        dp[i+1][less or d<max_d] = max(dp[i+1][less or d<max_d], dp[i][less]*2 + cnt[i+1][1-d])


print(max(dp[-1]))

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

b_len = len(format(max(A),'b'))
B = [[int(_) for _ in format(a, '0{}b'.format(b_len))] for a in A]
B_t = [list(b) for b in zip(*B)]
B_b = [int(sum(b)<=(N/2)) for b in B_t]
K_b = [int(_) for _ in bin(K)[2:]]


if len(K_b) > len(B_b):
    B_b = K_b[:(len(K_b)-len(B_b))] + B_b
else:
    K_b = [0]*(len(B_b)-len(K_b)) + K_b
import copy
x_b = copy.copy(B_b)
for i in range(len(K_b)):
    if B_b[i] == 0 and K_b[i] == 1:
        break
    elif B_b[i] == 1 and K_b[i] == 0:
        x_b[i] = 0

from functools import reduce

x = int(reduce(lambda x,y:x+y, [str(a) for a in x_b]), 2)

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

Solution (Python):
n, k = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]

v = [0] * 41
for x in a:
  for i in range(41):
    v[i] += x & 1
    x >>= 1

max_acc = 0
max_bit = 0
for i in range(41):
  if (k >> i) & 1:
    max_acc = max( (1 << i)*(n-v[i]) + max_acc,
                   (1 << i)*   v[i]  + max_bit )
  else:
    max_acc += (1 << i)*v[i]
  max_bit += (1 << i)*max(v[i], n-v[i])

print(max_acc)

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

MAX_DIGIT_LENGTH=50

dp=[[-1 for _ in range(2)] for _ in range(100)]
dp[0][0]=0

for d in range(MAX_DIGIT_LENGTH):
  mask=1<<((MAX_DIGIT_LENGTH-1)-d)
  
  tmp=0
  for a in A:
    if a&mask == mask:
      tmp+=1
      
  cost0=mask*tmp
  cost1=mask*(N-tmp)
    
  if dp[d][1]!=-1:
    dp[d+1][1]=max(dp[d][1]+max(cost0, cost1), dp[d+1][1])
  
  if dp[d][0]!=-1:
    if K&mask == mask:
      dp[d+1][1]=max(dp[d][0]+cost0, dp[d+1][1])
      dp[d+1][0]=max(dp[d][0]+cost1, dp[d+1][0])
    else:
      dp[d+1][0]=max(dp[d][0]+cost0, dp[d+1][0])
      
print(max(dp[MAX_DIGIT_LENGTH][0], dp[MAX_DIGIT_LENGTH][1]))

Solution (Python):
import math

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

if k == 0 and max(a) == 0:
    print(sum(a))
else:
    l = int(math.log2(max(k, max(a))))
    mask = int(math.pow(2, l))

    f = False
    gsum = 0

    for i in reversed(range(0, l + 1)):
        psum = 0
        for j in range(0, n):
            psum += 1 if (a[j] & mask) != 0 else 0 
        
        if f:
            if psum <= n // 2:
                gsum += mask * (n - psum)
            else:
                gsum += mask * psum
        else:
            if (k & mask) != 0:
                if psum > n // 2:
                    gsum += mask * psum
                    f = True
                else:
                    gsum += mask * (n - psum)
            else:
                gsum += mask * psum
        mask = mask >> 1
    print(gsum)

Solution (Python):
import fileinput


def to_bits(n):
    return [int(c) for c in "{0:b}".format(n)]


def from_bits(bits):
    r = 0
    for i, b in enumerate(bits):
        if b:
            r += 2**(len(bits)-i-1)
    return r


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


def get_bits(Kbits, i, s, A):
    if i < s:
        first_bit = Kbits[i]
        if first_bit > 0:
            r = ([1] + get_bits(Kbits, i+1, s, A)) if f(2**(s-i-1), A) > f(0, A) else ([0] + get_bits([1]*s, i+1, s, A))
        else:
            r = [0] + get_bits(Kbits, i+1, s, A)
    else:
        r = []
    return r


def algorithm(K, A):
    Kbits = to_bits(K)
    return f(from_bits(get_bits(Kbits, 0, len(Kbits), A)), A)


def pass_inputs(input_lines):
    N, K = [n for n in input_lines[0]]
    return algorithm(K, input_lines[1])


def convert_int(s):
    try:
        r = int(s)
    except ValueError:
        r = s
    return r


def run():
    out = pass_inputs([[convert_int(v) for v in l.strip().split(" ")] for l in fileinput.input()])
    print(out)


if __name__ == "__main__":
    run()

Solution (Python):


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

b = [0 for _ in range(40)]
for aa in a:
    for j in range(40):
        b[j] += (aa >> j) & 1

x = 0
for j in sorted(range(40), reverse=True):
    
    if x | (1 << j) <= K:
        if 2 * b[j] < N:
            x += (1 << j)
res = 0
for j in range(40):
    if (x >> j) & 1 == 1:
        res += (N - b[j]) * (1 << j)
    else:
        res += (b[j]) * (1 << j)

print(res)

Solution (Python):


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

s = [0 for _ in range(50)]


for t in a:
    for j in range(50):
        s[j] += (t >> j) & 1

temp = 0
for j in range(50, -1, -1):
    if temp | (1 << j) <= K:
        if s[j] * 2 < N:
            temp |= (1 << j)
ans = 0
for j in range(50):
    if (temp >> j) & 1 == 0:
        ans += s[j] << j
    else:
        ans += (N - s[j] << j)
print(ans)

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

powlist = [2**x for x in range(0,40)]
list1 = [0 for x in range(0,40)]
list0 = [0 for x in range(0,40)]
k = [0 for x in range(0,40)]

for x in range(0,N):
    for y in range(1,41):
        if A[x] >= powlist[-y]:
            A[x] = A[x] - powlist[-y]
            list1[-y] += 1
        else:
            list0[-y] += 1

for y in range(1,41):
        if B >= powlist[-y]:
            B = B - powlist[-y]
            k[-y] += 1

z = 0

for n in powlist:
    if n > K:
        break
    z = n

if z == 0:
    Kindex = 0
else:
    Kindex = powlist.index(z)

answer1 = 0
if K == 0:
    answer2 = 0
else:
    answer2 = powlist[Kindex]*list0[Kindex]

for x in range(0,Kindex):
    answer1 += powlist[x]*max(list1[x],list0[x])
for x in range(Kindex,40):
    answer1 += powlist[x]*list1[x]

for x in range(Kindex-1,-1,-1):
    if k[x] == 0:
        answer2 += powlist[x]*list1[x]
        continue
    if max(list1[x],list0[x]) == list1[x]:
        for y in range(0,x+1):
            answer2 += powlist[y]*max(list1[y],list0[y])
        break
    else:
        answer2 += powlist[x]*list0[x]

for x in range(Kindex+1,40):
    answer2 += powlist[x]*list1[x]

answer = max(answer1,answer2)

print(answer)

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

X = 0
k = 1 << 41
for _ in range(41):
  k = k >> 1
  if X + k > K:
    continue
  
  count = 0
  for i in range(N):
    if A[i] & k:
      count += 1
  
  if count < N / 2:
    X += k
    
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()))
bitcount = []
k += 1
m = k
f = [sum(a)]
while(m > 0 or max(a) > 0):
    odd = sum(list(map(lambda x: x%2, a)))
    bitcount.append(odd)
    a = list(map(lambda x: x//2, a))
    m = m//2
for keta in range(len(bitcount)):
    if k & (2 ** keta) != 0:
        ans = 0
        for i in range(keta):
            ans += max(bitcount[i], n - bitcount[i]) * 2 ** i
        for i in range(keta + 1, len(bitcount)):
            if k & (2 ** i) == 0:
                ans += bitcount[i] * 2 ** i
            else:
                ans += (n - bitcount[i]) * 2 ** i
        ans += bitcount[keta] * 2 ** keta
        f.append(ans)
print(max(f))

Solution (Python):
n,k = map(int,input().split())
k_keta = len(bin(k)) - 2
k_nisin = list(bin(k))
k_nisin.pop(0)
k_nisin.pop(0)
a = list(map(int,input().split()))
a_keta = len(bin(max(a))) - 2

fix = max(k_keta,a_keta)
nisin = []
for i in range(n):
    temp = list(bin(a[i]))
    temp.pop(0)
    temp.pop(0)
    for i in range(fix-len(temp)):
        temp.insert(0,"0")
    nisin.append(temp)

counter = []
for i in range(fix):
    temp = 0
    for k in range(n):
        if nisin[k][i] == "1":
            temp += 1
    counter.append(temp)

ans = [0 for i in range(k_keta)]
check = False 
for i in range(k_keta):
    if counter[-1-k_keta+1+i]*2 <= n:
        if k_nisin[i] == "1":
            ans[i] += 1
        else:
            if check:
                ans[i] += 1
    else:
        if k_nisin[i] == "1":
            check = True

ans.reverse()
x = 0 
c = 1
for i in range(len(ans)):
    x += ans[i] * c
    c = c*2

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

Solution (Python):
import sys
sys.setrecursionlimit(10*6)

def main():
	n, k = map(int, input().split())
	a = list(map(int, input().split()))
	m = 0
	ans = 0
	x = [0] * 50
	for i in range(50, -1, -1):
		temp = 2 ** i
		if temp > k:
			continue
		for j in range(n):
			if temp ^ (temp & a[j]) != 0:
				x[i] += 1
		if x[i] > n-x[i] and m + temp <= k:
			m += temp
	for i in range(n):
		ans += m ^ a[i]
	print(ans)

main()

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


X = 0
k = 1 << 41  


for _ in range(41):  
    k = k >> 1
    if X + k > K: continue  
    
    
    cnt = 0
    for i in range(N):
        if A[i] & k: cnt += 1
    
    
    if cnt < len(A)/2: X += k

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

Solution (Python):
def main():
    _, k = map(int, input().split())
    a = [int(s) for s in input().split()]

    print(solve(k, a))

def solve(k, a):
    b = max(k.bit_length(), max(ai.bit_length() for ai in a))
    dp = [[0, 0] for _ in range(b + 1)]

    mask = 1
    for i in range(1, b + 1):
        x = sum(ai & mask for ai in a)
        y = sum((ai ^ mask) & mask for ai in a)
        if k & mask != 0:
            dp[i][0] = max(x + dp[i-1][1], y + dp[i-1][0])
        else:
            dp[i][0] = x + dp[i-1][0]
        dp[i][1] = dp[i-1][1] + max(x, y)
        mask <<= 1
    
    return dp[b][0]

def build_table(k, a):
    dp = dict()
    dp[1] = (0, 0)

    mask = 1
    while mask < k * 2:
        x = sum(t & mask for t in a)
        y = sum((t & mask) ^ mask for t in a)
        dp[mask << 1] = (max(x, y), max(x, y) + dp[mask][1])
        mask = mask << 1

    return dp

def _solve(k, a):
    def memoize(f):
        memo = dict()
        def wrapped(k, mask):
            key = (k, mask)
            r = memo.get(key, None)
            if r is None:
                r = f(k, mask)
                memo[key] = r
            return r
        return wrapped
    
    @memoize
    def rec(k, mask):
        b = k.bit_length()
        return b
    
    b = max(k.bit_length(), max(x.bit_length() for x in a))
    mask = (1 << b) - 1
    return rec(k, mask)

main()

Solution (Python):
from collections import Counter
N,K = map(int,input().split())
sarr = list(map(int,input().split()))
arr = sorted(sarr)
def xsum(arr,n):
    s = 0
    for i in arr:
        s += n^i
    return s
c = Counter()
for i in arr:
    n = 1
    while n <= K:
        if i%2:
            c[n] += 1
        else:
            c[n] += 0
        n *= 2
        i = i >> 1
ans = 0
p = [1]
while(p[-1]*2 <= K):
    p.append(p[-1]*2)
for i in p[::-1]:
    if c[i] < N - c[i]:
        if ans + i <= K :
            ans += i
print(max(xsum(arr,ans),xsum(arr,K)))

Solution (Python):
from collections import Counter
N,K = map(int,input().split())
sarr = list(map(int,input().split()))
arr = sorted(sarr)
def xsum(arr,n):
    s = 0
    for i in arr:
        s += n^i
    return s
c = Counter()
for i in arr:
    n = 1
    while n <= K:
        if i%2:
            c[n] += 1
        else:
            c[n] += 0
        n *= 2
        i = i >> 1
ans = 0
p = [1]
while(p[-1]*2 <= K):
    p.append(p[-1]*2)
for i in p[::-1]:
    if c[i] < N - c[i]:
        if ans + i <= K :
            ans += i
print(max(xsum(arr,ans),xsum(arr,K)))

Solution (Python):
def calc(i, subed=False):
    if i >= len(k_bin):
        return 0
    pos = len(k_bin)-i-1

    max_val = 0
    if ones[pos] <= N//2 and (subed or k_bin[i] == '1'):
        max_val = (N-ones[pos]) * 2**pos + calc(i+1, subed)
    else:
        max_val = max(max_val, ones[pos] * 2**pos +
                      calc(i+1, True if k_bin[i] == '1' else subed))
    return max_val


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

max_length = 0

ones = [0] * 40
for a in As:
    a_bin = bin(a)[2:]
    max_length = max(max_length, len(a_bin))
    for i in range(len(a_bin)):
        if a_bin[i] == '1':
            pos = len(a_bin)-i-1
            ones[pos] += 1

k_bin = bin(K)[2:].rjust(max_length, "0")
print(calc(0))

Solution (Python):
import numpy as np

N, K = [int(a) for a in input().split()]
A = [int(a) for a in input().split()]

K = format(K, 'b')
B = [format(a, 'b') for a in A]
max_order = len(max(B + [K], key=len))

K = K.zfill(max_order)
B = np.array([list(b.zfill(max_order)) for b in B], dtype='i')
B = B.sum(axis=0)
B = np.where(B < N/2, '1', '0')

for i, k, b in zip(range(max_order), K, B):
    if k < b:
        B[i] = '0'
    elif k > b:
        break

X = int(''.join(map(str, B)), 2)

print(sum(map(lambda a: X ^ a, A)))

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

x = 0
b = 1 << 50
for _ in range(50):
    b = b >> 1
    if x + b > k:
        continue;

    cnt = 0
    for i in a:
        if i & b:
            cnt += 1

    if cnt < len(a) / 2:
        x += b

ans = 0
for i in a:
    ans += i ^ x

print(ans)

Solution (Python):
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,*a=map(int,open(0).read().split());t,s=2**40,0
while t:
 c=sum((i&t)//t for i in a)
 if k<t or c*2>=n:s+=t*c
 else:s+=t*(n-c);k-=t
 t//=2
print(s)

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
one = [sum([(a[j]>>i)&1 for j in range(n)]) for i in range(40)]
zero = [n - one[i] for i in range(40)]
dp = [[-float("inf") for _ in range(2)] for _ in range(41)]
dp[40][0] = 0
for i in range(39, -1, -1):
	if (k>>i)&1 == 0:
		dp[i][0] = dp[i+1][0] + (2**i) * one[i]
		dp[i][1] = dp[i+1][1] + (2**i) * max(one[i], zero[i])
	else:
		dp[i][0] = dp[i+1][0] + (2**i) * zero[i]
		dp[i][1] = max(dp[i+1][0] + (2**i) * one[i], dp[i+1][1] + (2**i) * max(one[i], zero[i]))

print(max(dp[0]))

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):


if __name__ == "__main__":

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

    p = [1] * 41
    for i in range(40):
        p[i+1] = p[i] * 2
        
    ans = 0
    x = 0
    for i in range(41):
        t = p[40-i]
        if x + t > k:
            cnt = 0
            for j in range(n):
                if an[j] & t == t:
                    cnt += 1
            ans += cnt * t
        else:
            cnt = 0
            for j in range(n):
                if an[j] & t == t:
                    cnt += 1
            if cnt <= n/2:
                x += t
            ans += max(cnt, n-cnt) * t
    print(ans)

Solution (Python):
def f(x, a_list):
    return sum(map(lambda y: y ^ x, a_list))

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

bit_num = len(bin(K)) - 2
dp = ["0" for _ in range(bit_num)]

for i in range(bit_num):
    bits = dp[:i]

    one = bits + ["1"] + ["0"] * (bit_num - i - 1)
    zero = bits + ["0"] + ["0"] * (bit_num - i - 1)

    if f(int("".join(one), 2), a_list) > f(int("".join(zero), 2), a_list) and int("".join(one), 2) <= K:
        dp[i] = "1"
    else:
        dp[i] = "0"
print(f(int("".join(dp), 2), a_list))

Solution (Python):
L = 50

def get_binary_str(n: int) -> str:
    binary = bin(n)[2:]
    padding_length = L - len(binary)
    return '0' * padding_length + binary

def get_first_one_pos(s: str) -> int:
    i = 0
    while i < len(s) and s[i] == '0':
        i += 1
    return i

def xor(x: int, y: int) -> int:
    if x == y:
        return 0
    else:
        return 1

def calc_xor(i: int, x: int, binary_As) -> int:
    ret = 0
    for binary_A in binary_As:
        ret += xor(x, int(binary_A[i]))
    return ret


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

binary_As = [get_binary_str(A) for A in As]
binary_K = get_binary_str(K)
one_pos = get_first_one_pos(binary_K)

i = 0
ret = 0
while i < one_pos:
    ret += calc_xor(i, 0, binary_As) * 2**(L-i-1)
    i += 1

flag = False
while i < L:
    a = calc_xor(i, 0, binary_As)
    b = N - a
    if flag:
        ret += a * 2**(L-i-1) if a > b else b * 2**(L-i-1)
    else:
        if binary_K[i] == '1':
            if a > b:
                flag = True
            ret += a * 2**(L-i-1) if a > b else b * 2**(L-i-1)
        else:
            ret += a * 2**(L-i-1)

    i += 1

print(ret)