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

Bit = 0
while(True):
    if((1<<(Bit+1))>K):  
        break
    else:
        Bit += 1
X = 0
for b in range(Bit,-1,-1):
    X_ = X+(1<<b)
    if(X_ > K):
        continue
    Sum = sum([X^a for a in A])
    Sum_ = sum([X_^a for a in A])
    if(Sum_ > Sum):
        X = X_
print(sum([X^a for a in A]))

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


MAX=max(len(bin(K)[2:]), len(bin(max(A))[2:]))


L=[[0]*MAX for _ in range(N)]
for i,a in enumerate(A):
    b=bin(a)[2:]
    b=b.zfill(MAX)
    for j,s in enumerate(b):
        if s=="1":
            L[i][j]+=1
L=np.array(L)
count=0
ones=L.sum(axis=0)

for i in range(MAX):
    if ones[i]*2==N:
        continue
    elif ones[i]*2<N:
        add=2**(MAX-1-i)
        if count+add<=K:
            count+=add
    else:
        continue

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

Solution (Python):
N,K=map(int,input().split())
A=list(map(int, input().split()))
dp=[[0,0]for _ in range(42)]


for i in range(1,42):
  if dp[i-1][1]==1:
    dp[i][1]=1
  
  cnt=0
  
  for j in range(N):
    if (A[j]>>(41-i))&1==1:
      cnt+=1
      
  
  if cnt>=N-cnt:
    dp[i][0]=dp[i-1][0]+(2**(41-i))*cnt
    if (K>>(41-i))&1==1:
      dp[i][1]=1
  else:
    if dp[i][1]==1:
      dp[i][0]=dp[i-1][0]+(2**(41-i))*(N-cnt)
    else:
      if (K>>(41-i))&1==1:
        
        dp[i][0]=dp[i-1][0]+(2**(41-i))*(N-cnt)
      else:
        
        dp[i][0]=dp[i-1][0]+(2**(41-i))*cnt
print(dp[41][0])

Solution (Python):
import sys
readline = sys.stdin.readline
MAX_DIGIT = 40

def main():
    N, K = map(int, readline().rstrip().split())
    K_bin = bin(K)[2:].zfill(MAX_DIGIT)
    A = list(map(int, readline().rstrip().split()))
    A = [bin(a)[2:].zfill(MAX_DIGIT) for a in A]
    dp = [[-1] * 2 for _ in range(MAX_DIGIT+1)]
    

    dp[0][0] = 0
    mul = 2 ** (MAX_DIGIT - 1)
    for d in range(MAX_DIGIT):
        cnt = len([1 for a in A if a[d] == '1'])  
        gain0 = cnt * mul
        gain1 = (N - cnt) * mul

        
        if dp[d][1] != -1:
            
            dp[d+1][1] = max(dp[d+1][1], dp[d][1] + max(gain0, gain1))
        
        
        if dp[d][0] != -1:
            
            if K_bin[d] == '1':
                dp[d+1][1] = max(dp[d+1][1], dp[d][0] + gain0) 

        
        if dp[d][0] != -1:
            
            if K_bin[d] == '1':
                dp[d+1][0] = max(dp[d+1][0], dp[d][0] + gain1)
            else:
                dp[d+1][0] = max(dp[d+1][0], dp[d][0] + gain0)
        
        mul //= 2
    
    print(max(dp[MAX_DIGIT]))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
readline = sys.stdin.readline
MAX_DIGIT = 40

def main():
    N, K = map(int, readline().rstrip().split())
    K_bin = bin(K)[2:].zfill(MAX_DIGIT)
    A = list(map(int, readline().rstrip().split()))
    A = [bin(a)[2:].zfill(MAX_DIGIT) for a in A]
    dp = [[-1] * 2 for _ in range(MAX_DIGIT+1)]
    

    dp[0][0] = 0
    mul = 2 ** (MAX_DIGIT - 1)
    for d in range(MAX_DIGIT):
        cnt = len([1 for a in A if a[d] == '1'])  
        cost0 = cnt * mul
        cost1 = (N - cnt) * mul

        
        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_bin[d] == '1':
                dp[d+1][1] = max(dp[d+1][1], dp[d][0] + cost0) 

        
        if dp[d][0] != -1:
            
            if K_bin[d] == '1':
                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)
        
        mul //= 2
    
    print(max(dp[MAX_DIGIT]))


if __name__ == '__main__':
    main()

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

X = 0
bit_l = 0
while K >= (1 << bit_l):
    bit_l += 1
bit_l -= 1

while bit_l >= 0:
    one = 0
    for a in A:
        one += int(((a >> bit_l) & 1) == 1)
    if one < N - one and (X | (1 << bit_l)) <= K:
        X = X | (1 << bit_l)
    bit_l -= 1

ans = sum([a ^ X for a in A])
print(ans)

Solution (Python):

from collections import defaultdict



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

"""
・K以下の非負整数の範囲で〜：桁DP感ある
・XORをとる：桁ごとに確認できる
・Xを選んで、f = X xor A1 + X xor A2 + ... + X xor AN
　 -> それぞれのAと毎回 xor 取るのではなく、桁ごとに xor を取ることができる　←　超重要のはず
　 -> A1 ~ AN の各桁（2進数の時の）に1が立っているのが何個あるか数えておく


遷移
dp[i][1] -> dp[i+1][1] : i-1桁目まででK未満が確定していれば、i桁目に1,0どちらを選んでもK未満
dp[i][0] -> dp[i+1][1]  : i-1桁目まででKと一致している場合、Kのi桁目が1なら、Xで0を選べば遷移できる
dp[i][0] -> dp[i+1][0]  : i桁目まで一致させる場合
"""

d = defaultdict(int)
for a in A:
    for i in range(45):
        if a & (1 << i):
            d[i] += 1


dp = [[-1 for _ in range(2)] for _ in range(45+1)]

dp[0][0] = 0

for i in range(45):

    
    if K & (1 << (45 - 1 - i)):
        is_one = True
    else:
        is_one = False

    
    p0 = (2**(45-1-i)) * d[45-1-i]
    p1 = (2**(45-1-i)) * (N - d[45-1-i])

    
    if dp[i][1] != -1:
        dp[i+1][1] = dp[i][1] + max(p1, p0)

    
    if dp[i][0] != -1:
        if is_one:
            dp[i+1][1] = max(dp[i+1][1], dp[i][0] + p0)
    
    
    if dp[i][0] != -1:
        if is_one:
            dp[i+1][0] = dp[i][0] + p1
        else:
            dp[i+1][0] = dp[i][0] + p0
    


print(max(dp[-1]))

Solution (Python):


import sys
import math





















def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n, k = mi()
    A = lmi()

    max_digit_len = int(math.log(max(max(A), k), 2)) + 1
    digit = [[0, 0] for _ in range(max_digit_len)]
    for num in A:
        bin_num_str = bin(num)[2:]
        for i in range(max_digit_len):
            if i < len(bin_num_str):
                j = len(bin_num_str) - i - 1
                digit[i][int(bin_num_str[j])] += 1    
            else:
                digit[i][0] += 1    
    
    
    
    def calc_max_xor_sum(digit, num, num_digit):
        '下から num_digit 桁を自由に使い num 以下の数字を構成していい時、その桁の範囲での xor sum の最大値を返す'
        if num_digit == 0:
            return 0
        
        
        if num >= pow(2, num_digit) - 1:
            tmp = 0
            for i in range(num_digit):
                tmp += pow(2, i) * max(digit[i][0], digit[i][1])
            return tmp

        
        pattern_0 = pow(2, num_digit - 1) * digit[num_digit - 1][1]    
        pattern_0 += calc_max_xor_sum(digit, num, num_digit - 1)
        
        
        if pow(2, num_digit - 1) > num:
            pattern_1 = 0
        else:
            pattern_1 = pow(2, num_digit - 1) * digit[num_digit - 1][0]    
            pattern_1 += calc_max_xor_sum(digit, num - pow(2, num_digit - 1), num_digit - 1)
        
        
        return max(pattern_0, pattern_1)


    k_digit_len = int(math.log(k, 2)) + 1 if k != 0 else 1
    ans = 0
    if k_digit_len < max_digit_len:
        for i in range(k_digit_len, max_digit_len):
            
            ans += pow(2, i) * digit[i][1]

    
    ans += calc_max_xor_sum(digit, k, k_digit_len)
    print(ans)



if __name__ == "__main__":
    main()

Solution (Python):
n,k = map(int,input().split())
a = list(map(int,input().split()))
b0 = [n]*41
b1 = [0]*41
ans = 0
temp = 0
for i in a:
    bit = bin(i)
    for j in range(len(bit)-2):
        t = (int(bit[-j-1]) == 1)
        b0[-j-1] -= t
        b1[-j-1] += t


for i in range(41):
    if temp + 2**(40-i) <= k and b0[i] > b1[i]:
        temp += 2**(40-i)
        ans += 2**(40-i) * b0[i]
    else:
        ans += 2**(40-i) * b1[i]

print(ans)

Solution (Python):
N, K = map(int, input().split())
A = tuple(map(int, input().split()))
X = 0
for i in range(len(bin(K)) - 2, -1, -1):
    if (X + (1 << i)) > K:
        continue
    if sum((a >> i) & 1 for a in A) * 2 < N:
        X += (1 << i)
print(sum(a ^ X for a in A))

Solution (Python):
n, k = [int(x) for x in input().split()]
a_list = [int(x) for x in input().split()]
s=0
l = len(bin(k)) - 2
b = n / 2
x = 0
for i in range(l, -1, -1):
    count = sum([(a >> i) & 1 for a in a_list])
    if count < b:
        temp = 1 << i
        if x + temp <= k:
            x += temp
print(sum([x ^ a for a in a_list]))

Solution (Python):
def max_f(K, A):
    K += 1
    N = len(A)
    len_K = len('{:b}'.format(K))
    max_KA = max([K, max(A)])
    max_len = len('{:b}'.format(max_KA))
    bin_K = '{{:0{}b}}'.format(max_len).format(K)
    bin_A = ['{{:0{}b}}'.format(max_len).format(a) for a in A]
    bit_A_sum = [sum([int(bin_str[-(i+1)]) for bin_str in bin_A]) for i in range(max_len)]
    bit_K = [int(bin_K[-(i+1)]) for i in range(max_len)]
    f_val = [0 for _ in range(len_K)]
    for free_len in range(len_K):
        if bit_K[free_len] == 0:
            continue
        digit_x = [0 for _ in range(max_len)]
        for j, (ba, bk) in enumerate(zip(bit_A_sum, bit_K)):
            if j < free_len:
                digit_x[j] = max([ba, N - ba])
            elif j == free_len:
                
                digit_x[j] = ba
            else:
                digit_x[j] = ba if bk == 0 else (N - ba)
        f_val[free_len] = sum([(2**i) * d for i, d in enumerate(digit_x)])
    return int(max(f_val))


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


if __name__ == '__main__':
    main()

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

a.sort()

length = len(format(a[-1],'b'))
string = '0'+str(length)+'b'

ans = 0
while True:
	k_length = len(format(k,'b'))
	if length < k_length:
		ans += n * (2**(k_length - 1))
		k -= 2**(k_length - 1)
	else:
		break

l = [0 for _ in range(length)]

for i in range(len(a)):
	tmp = tuple(format(a[i],string))
	for j in range(length):
		if tmp[j] == '0':
			l[j] += 1

res = '0b'
num = 0
tmp = 2 ** length
for i in range(len(l)):
	tmp //= 2
	if l[i] > n // 2 and num + tmp <= k:
		res = res + '1'
		num += tmp
	else:
		res = res + '0'

x = int(res,2)

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

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

if k == 0:
    print(sum([0 ^ a for a in a_list]))
    exit()

l = len(bin(k)) - 2
b = n / 2
x = 0
for i in range(l, -1, -1):
    count = sum([(a >> i) & 1 for a in a_list])
    if count < b:
        temp = 1 << i
        if x + temp <= k:
            x += temp
print(sum([x ^ a for a in a_list]))

Solution (Python):
N, K = map(int,input().split())
A = list(map(int,input().split()))
L = [0 for _ in range(40)]
for a in A:
    for i in range(40):
        L[i] += a & 1
        a >>= 1
L.reverse()
K = '{:040b}'.format(K)
dp1 = [0 for _ in range(41)]
dp2 = [0 for _ in range(41)]

for i in range(40):
    dp1[i+1] += 2 * dp1[i]
    if K[i] == '0':
        dp1[i+1] += L[i]
    else:
        dp1[i+1] += N - L[i]
    if dp2[i] != 0:
        dp2[i+1] = 2 * dp2[i] + max(L[i], N - L[i])
    if K[i] == '1':
        dp2[i+1] = max(dp2[i+1], 2 * dp1[i] + L[i])

ans = max(dp1[40], dp2[40])

print(ans)

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
keta_a = [0]*41
bin_k = format(k, 'b').zfill(41)
for i in a:
  bin_a = str(format(i, 'b'))
  for j in range(len(bin_a)):
    if bin_a[-j-1] == '1':
      keta_a[-j-1]+=1
dp = [[0]*2 for _ in range(41)] 
flag = True
for i in range(1, 41):
  if flag:
    if bin_k[i] == '0':
      dp[i][0] = dp[i-1][0]+2**(40-i)*keta_a[i]
    if bin_k[i] == '1':
      flag = False
      dp[i][0] = dp[i-1][0]+2**(40-i)*(n-keta_a[i])
      dp[i][1] = dp[i-1][0]+2**(40-i)*keta_a[i]
  else:
    if bin_k[i] == '0':
      dp[i][0] = dp[i-1][0]+2**(40-i)*keta_a[i]
      dp[i][1] = dp[i-1][1] + 2**(40-i)*max(n-keta_a[i], keta_a[i])
    if bin_k[i] == '1':
      dp[i][0] = dp[i-1][0] + 2**(40-i)*(n-keta_a[i])
      dp[i][1] = max(dp[i-1][0] + 2**(40-i)*(keta_a[i]),dp[i-1][1] + 2**(40-i)*max(n-keta_a[i], keta_a[i]))
print(max(dp[40][0], dp[40][1]))

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, k, *a = map(int, read().split())
v = 0
ans = 0
for i in range(40, -1, -1):
    cnt = 0
    for aa in a:
        if (aa >> i) & 1:
            cnt += 1
    if n - cnt > cnt and v + (1 << i) <= k:
        v += 1 << i
        ans += (n - cnt) * (1 << i)
    else:
        ans += cnt * (1 << i)
print(ans)

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

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
l = len(bin(k))-2
if k == 0:
    l = 0
memo = [0 for i in range(l)]

for ai in a:
    for j in range(l):
        if ai & (1<<j):
            memo[j] += 1

x = 0
f = 0

for j in reversed(range(l)):
    if f or k & (1<<j):
        if memo[j] <= n - memo[j]:
            x += 2 ** j
        else:
            f = 1
ans = 0

for ai in a:
    ans += ai ^ x

print(ans)

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
l = len(bin(k))-2
if k == 0:
    l = 0
memo = [0 for i in range(l)]

for ai in a:
    for j in range(l):
        if ai & (1<<j):
            memo[j] += 1

x = 0
f = 0

for j in reversed(range(l)):
    if f or k & (1<<j):
        if memo[j] < n - memo[j]:
            x += 2 ** j
        else:
            f = 1
ans = 0

for ai in a:
    ans += ai ^ x

print(ans)

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
_LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N,K = LI()
A = LI()
max_bit = (10**12).bit_length()
bit = [0 for _ in range(max_bit)]
for x in A:
    b = 1
    for j in range(max_bit):
        if x & b: bit[j] += 1
        b <<= 1

ans = 0
k = 0
for i in range(max_bit-1,-1,-1):
    b = bit[i]
    if k + 2**i <= K and bit[i]*2 < N:
        b = N - b
        k += 2**i
    ans += b * 2**i
print (ans)

Solution (Python):
n, k = map(int, input().split())
A = list(map(int, input().split()))
one = [0] * 40
zero = [0] * 40
for i in range(40):
    for a in A:
        if a >> i & 1:
            one[i] += 1
        else:
            zero[i] += 1
dp1 = [-1e10] * 41 
dp2 = [-1e10] * 41 
dp1[40] = 0
for i in range(39, -1, -1):
    if k >> i & 1:
        dp2[i] = max(dp2[i + 1] * 2 + max(zero[i], one[i]), dp1[i + 1] * 2 + one[i])
        dp1[i] = dp1[i + 1] * 2 + zero[i]
    else:
        dp2[i] = dp2[i + 1] * 2 + max(zero[i], one[i])
        dp1[i] = dp1[i + 1] * 2 + one[i]
print(max(dp1[0], dp2[0]))

Solution (Python):
n,k = map(int,input().split())
A = list(map(int,input().split()))
cnt = [0]*50
for a in A:
    i = 0
    while a > 0:
        if a&1:
            cnt[i] += 1
        i += 1
        a = a >> 1
base = 0
delta = [0]*50
pow2 = 1
s = [0]*51
for i,c in enumerate(cnt):
    delta[i] = max(0,pow2*(n - 2*c))
    base += pow2*c
    s[i+1] = s[i] + delta[i]
    pow2*=2
i = 0
K = []
ans = 0
while k > 0:
    if k&1:
        K.append(i)
        ans += delta[i]
    i += 1
    k = k >> 1
done = 0
for i in K[::-1]:
    ans = max(ans, done + s[i])
    done += delta[i]
print(ans + base)

Solution (Python):
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,k = na()
a = na()
b = [0]*40

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

ans = 0
for i in range(40)[::-1]:
    if b[i] < n/2:
        ans += 1<<i
    if ans > k:
        ans -= 1<<i

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

print(bns)

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
One=[0]*40
OneK=format(K, '040b')
flg=True
for i in range(40):
  for j in range(N):
    if A[j]==0:
      continue
    flg=False
    One[39-i]+=A[j]&1
    A[j]=A[j]>>1
  if flg:
    break
  flg=True
ans=0
i=0
while i<40:
  if OneK[i]=='1':
    break
  ans+=pow(2,39-i)*One[i]
  i+=1
while i<40:
  if One[i]>=N/2:
    ans+=pow(2,39-i)*One[i]
    if OneK[i]=='1':
      i+=1
      break
  elif OneK[i]=='1':
    ans+=pow(2,39-i)*(N-One[i])
  else:
    ans+=pow(2,39-i)*One[i]
  i+=1
while i<40:
  ans+=pow(2,39-i)*max(One[i],(N-One[i]))
  i+=1
print(ans)

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
One=[0]*40
OneK=format(K, '040b')
flg=True
for i in range(40):
  for j in range(N):
    if A[j]==0:
      continue
    flg=False
    One[39-i]+=A[j]&1
    A[j]=A[j]>>1
  if flg:
    break
  flg=True
ans=0
i=0
while i<40:
  if OneK[i]=='1':
    break
  ans+=pow(2,39-i)*One[i]
  i+=1
flg=False
while i<40:
  if One[i]>=N/2:
    ans+=pow(2,39-i)*One[i]
    if OneK[i]=='1':
      flg=True
  else:
    if flg or OneK[i]=='1':
      ans+=pow(2,39-i)*(N-One[i])
    else:
      ans+=pow(2,39-i)*One[i]
  i+=1
print(ans)

Solution (Python):
inf = 10**9+7
mod = 10**9+7
n, k = map(int, input().split())
a = list(map(int, input().split()))
rep = len(bin(k)) - 2
ans = 0
totala = 0
if k != 0:
    for i in range(rep):
        count1 = 0
        count0 = 0
        for j in range(n):
            if ((a[j] >> (rep-1-i)) & 1): 
                count0+=1
            else:
                count1+=1
        if count1 > count0:
            ans += (2**(rep-1-i))
    anslist = []
    for i in range(rep):
        tmp = 0
        if (k >> (rep-1-i) & 1):
            for j in range(rep):
                if j > i:
                    tmp+=(ans>>(rep-1-j) & 1)*(2**(rep-1-j))
                if j < i:
                    tmp+=(k>>(rep-1-j) & 1)*(2**(rep-1-j))
            anslist.append(tmp)
    anslist.append(k)
    for num in anslist:
        total = 0
        for i in range(n):
            total += (num ^ a[i])
        totala = max(totala, total)
else:
    for i in range(n):
        totala += (ans ^ a[i])

print(totala)

Solution (Python):

import sys
from functools import lru_cache
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
A = np.array(lr(), np.int64)
limit = int(max(A.max(), K)).bit_length()
bit_cnt = [((A>>k)&1).sum() for k in range(limit)]

@lru_cache(None)
def solve(K, index):
    if index < 0:
        return 0
    bit = 1 << index
    
    ret = (bit_cnt[index]<<index) + solve(min(K, bit-1), index-1)
    if bit <= K:
        ret = max(ret, ((N-bit_cnt[index])<<index) +  solve(K-bit, index-1))
    return ret

answer = solve(K, limit-1)
print(answer)

Solution (Python):

import sys
import numpy as np
from functools import lru_cache

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


N, K = lr()
A = lr()
limit = max(max(A), K).bit_length()
X = [0] * (limit)
for a in A:
    for i in range(limit):
        if (a >> i) & 1:
            X[i] += 1

Y = [max(x, N-x) for x in X]

@lru_cache(None)
def cal(index, total):
    total += sum([y * 2 ** i for i, y in enumerate(Y[:index+1])])
    return total

@lru_cache(None)
def dfs(index, sum, y):
    if index == limit:
        return sum
    i = limit - 1 - index
    if y + 2 ** (i + 1) <= K:
        return cal(i, sum)
    ret = dfs(index+1, sum + X[i] * 2 ** i, y)
    if y + 2 ** i <= K:
        ret = max(ret, dfs(index+1, sum+(N-X[i])*2**i, y+2**i))
    return ret

answer = dfs(0, 0, 0)
print(answer)

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

x = 0
ans = 0
for i in range(45,-1,-1):
    count = 0
    for j in a:
        if (j >> i) & 1:
            count += 1
    
    if n-count > count and x + (1<<i) <= k:
        ans += (n-count)* (1<<i)
        x += 1<<i
    else:
        ans += count*(1<<i)
print(ans)

Solution (Python):

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


N, K = lr()
A = lr()
limit = max(max(A), K).bit_length()
X = [0] * (limit)
for a in A:
    for i in range(limit):
        if (a >> i) & 1:
            X[i] += 1

Y = [max(x, N-x) for x in X]

def cal(index, total):
    total += sum([y * 2 ** i for i, y in enumerate(Y[:index+1])])
    return total

def dfs(index, sum, y):
    if index == limit:
        return sum
    i = limit - 1 - index
    if y + 2 ** (i + 1) <= K:
        return cal(i, sum)
    ret = dfs(index+1, sum + X[i] * 2 ** i, y)
    if y + 2 ** i <= K:
        ret = max(ret, dfs(index+1, sum+(N-X[i])*2**i, y+2**i))
    return ret

answer = dfs(0, 0, 0)
print(answer)

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

c = [0]*50

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

s = bin(k)
x = s[2:]


dp = [[0]*2 for i in range(len(x))]
if k != 0:
    dp[0][1] = pow(2,len(x)-1)*(n-c[len(x)-1])
    dp[0][0] = pow(2,len(x)-1)*(c[len(x)-1])
for i in range(1,len(x)):
    dp[i][0] = dp[i-1][0]+pow(2,len(x)-1-i)*max(n-c[len(x)-1-i],c[len(x)-1-i])
    if x[i] == "0":
        dp[i][1] = dp[i-1][1]+pow(2,len(x)-1-i)*c[len(x)-1-i]
    else:
        dp[i][1] = dp[i-1][1]+pow(2,len(x)-1-i)*(n-c[len(x)-1-i])
        dp[i][0] = max(dp[i][0],dp[i-1][1]+pow(2,len(x)-1-i)*(c[len(x)-1-i]))
ans = max(dp[-1])
for i in range(len(x),50):
    if c[i]>0:
        ans += pow(2,i)*c[i]
print(ans)

Solution (Python):
nim,mike = map(int,input().split())

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

counter = 0
for i in range(40,-1,-1):
    if counter | (1 << i) > mike:
        continue
    cnt = 0
    for j in range(nim):
        if array[j] & (1 << i) == 0:
            cnt += 1
    
    if cnt > nim - cnt:
        counter = counter | (1 << i)

result = 0
for i in range(nim):
    result += counter ^ array[i]

print(result)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
def digits_count(n):
  cnt = 0
  while n != 0:
    cnt += 1
    n //= 2
  return cnt
M = digits_count(max(max(A), K))
L = digits_count(K)
X = [0 for _ in range(M)] 
B = [1 for _ in range(M)]
for i in range(M-1):
  B[i+1] = B[i] * 2
for i in range(M):
  for j in range(N):
    X[i] += A[j] % 2
    A[j] //= 2
S = 0
for i in range(L, M):
  S += B[i] * X[i]
def XXOR(m, n):
  if n == 0:
    val = 0
    for i in range(m):
      val += B[i] * X[i]
    return val
  else:
    d = (n // B[m-1]) % 2
    if d == 1:
      left = B[m-1] * X[m-1]
      for i in range(m-1):
        left += max(X[i], N - X[i]) * B[i]
      return max(XXOR(m-1, n - B[m-1]) + (N - X[m-1]) * B[m-1], left)
    else:
      return XXOR(m-1, n) + X[m-1] * B[m-1]
print(XXOR(L, K) + S)

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

X=0
for i in range(40,-1,-1):
    b = 1<<i
    if X|b>K:continue
    c=0
    for a in A:
        if a&b: c+=1
    if c <= N//2: X|=b

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

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=0
co=[0]*50
check=False
for i in range(49,-1,-1):
    for j in range(n):
        if (a[j]>>i)&1:
            co[i]+=1
    if (k>>i)&1:
        if co[i]>=n-co[i]:
            ans+=(co[i]*(2**i))
            check=True
        else:
            ans+=((n-co[i])*(2**i))
    else:
        if check:
            if co[i]>=n-co[i]:
                ans+=(co[i]*(2**i))
            else:
                ans+=((n-co[i])*(2**i))
        else:
            ans+=(co[i]*(2**i))
print(ans)

Solution (Python):
import math

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

B = [[0] * 2 for _ in range(40)]

for i in range(N):
  Ai = A[i]
  for j in range(40):
    if Ai % 2 == 0:
      B[j][0] += 1
    else :
      B[j][1] += 1
    Ai = Ai // 2
    

Xmax = 0
if K != 0:

  Kd = int(math.log2(K))+1

  for i in range(Kd-1,-1,-1):
    if B[i][0] > B[i][1]:
      Xmax += 2**i
      if Xmax > K:
        Xmax -= 2**i
    
ans = 0
for i in range(N):
  ans += Xmax ^ A[i]

print(ans)

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



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





check_K = True
max_x = 0
for i, d in enumerate(reversed(digits)):
    i = 40 - i - 1
    if check_K and (K >> i) & 1 == 0:
        continue
    if d <= (N-d) and (K >> i) & 1 == 1:
        
        max_x += 2 ** i
    elif d <= (N-d) and not check_K:
        
        max_x += 2 ** i
    elif (K >> i) & 1 == 1:
        
        check_K = False



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

print(ans)

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



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





check_K = True
max_x = 0
for i, d in enumerate(reversed(digits)):
    i = 40 - i - 1
    if check_K and K < pow(2, i):
        continue
    if d <= (N-d) and ((K >> i) & 1 == 1 or not check_K):
        max_x += 2 ** i
    elif (K >> i) & 1 == 1:
        check_K = False
    

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

print(ans)

Solution (Python):
n,k=map(int,input().split())
A=list(map(int,input().split()))
m=max(k,max(A))
l=len(bin(m))-2
C=[0]*l
for a in A:
    for i in range(l):
        if (a>>i)&1:
            C[-i-1]+=1
One=[] 
Zero=[] 
for i in range(l):
    One.append(2**(l-i-1)*(n-C[i]))
    Zero.append(2**(l-i-1)*C[i])

b=bin(k)[2:]
lb=len(b)

cnt=0
if lb<l: 
    cnt=sum(Zero[:(l-lb)])
dp1=[One[l-lb]] 
dp2=[Zero[l-lb]] 

for i in range(1,lb):
    a1=One[l-lb+i]
    a0=Zero[l-lb+i]
    if b[i]=="1":
        dp1.append(dp1[-1]+a1)
        dp2.append(max(dp1[-2]+a0,dp2[-1]+max(a1,a0)))
    else:
        dp1.append(dp1[-1]+a0)
        dp2.append(dp2[-1]+max(a1,a0))

if k==0:
    print(cnt+dp2[0])
else:
    print(cnt+max(dp1[-1],dp2[-1]))

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
d=[0 for _ in range(40)]
att=[[0,i] for i in range(40)]
x=0
s=sum(A)
num=0
for i in range(N):
    x=A[i]
    for j in range(40):
        if (x>>j)&1:
            d[j]=d[j]+1

for i in range(40):
    att[i][0]=(N-2*d[i])*pow(2,i)
att.sort(key=lambda x:x[0],reverse=True)

for i in range(40):
    if (att[i][0]>0)and(num+pow(2,att[i][1])<=K):
        s=s+att[i][0]
        num=num+pow(2,att[i][1])
print(s)

Solution (Python):
from math import factorial
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def MI(): return map(int, input().split())


def S(): return input()


def MS(): return map(str, input().split())


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


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = {False: 'No', True: 'Yes'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']



show_flg = True


def main():
    N, K = MI()
    A = LI()
    LEN = 61
    ans = 0

    for d in range(LEN, -2, -1):
        if d != -1 and (K & (1 << d)) == False:
            continue

        tmp = 0
        for e in range(LEN, -1, -1):
            mask = 1 << e
            num = 0
            for j in range(N):
                if A[j] & mask > 0:
                    num += 1

            if e > d:
                if K & mask > 0:
                    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)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):


import sys
input = lambda: sys.stdin.readline().rstrip()

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

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




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

for d in range(50):
    mask = 1 << (50 - d - 1)

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

    
    add0 = mask * num
    
    add1 = mask * (N - num)

    
    if dp[d][1] != -1:
        dp[d+1][1] = max(dp[d+1][1], dp[d][1] + max(add0, add1))

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

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

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

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
if k==0:
    ans=0
    for i in a:
        ans+=i^0
    print(ans)
    exit()
l=k.bit_length()-1
dp=[[0,0] for i in range(l+1)]
M=0
for i in a:
    if i>>l&1:
        dp[0][1]+=1<<l
    else:
        dp[0][0]+=1<<l
    M=max(M,i)
p=0
M=M.bit_length()
for i in range(l+1,M):
    for j in a:
        if j>>i&1:
            p+=1<<i
dp[0][0]+=p
dp[0][1]+=p
for i in range(l):
    b=[0,0]
    p=l-i-1
    for j in a:
        if j>>p&1:
            b[0]+=1
        else:
            b[1]+=1
    b[0]<<=p
    b[1]<<=p
    for smaller in range(1,-1,-1):
        if smaller:
            dp[i+1][1]=dp[i][1]+max(b)
        else:
            if k>>p&1:
                dp[i+1][1]=max(dp[i+1][1],dp[i][0]+b[0])
                dp[i+1][0]=dp[i][0]+b[1]
            else:
                dp[i+1][0]=dp[i][0]+b[0]

print(max(dp[l]))

Solution (Python):
import sys
input = sys.stdin.buffer.readline
import numpy as np

def main():
    N,K = map(int,input().split())
    a = list(map(int,input().split()))
    l = max(max(a),K).bit_length()
    a = np.array(a)
    num,ans = 0,0
    for i in reversed(range(l)):
        base = 2**i
        bit = (a>>i)&1
        cnt = np.count_nonzero(bit)
        
        if cnt <= (N-1)//2:
            if num+base <= K:
                num += base
                ans += base*(N-cnt)
            else:
                ans += base*cnt
        else:
            ans += base*cnt
    
    print(ans)

if __name__ == "__main__":
    main()