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):
from collections import defaultdict
x,y=map(int,input().split())
a=list(map(int,input().split()))
lol=[]
for i in a:
    b=bin(i)[2:]
    lol.append("0"*(40-len(b))+b)
d=defaultdict(int)
for i in lol:
    for j in range(1,41):
        if i[-j]=="1":
            d[j]+=1
        else:
            d[j]-=1
            
s=""      
p=0
for i in range(1,41):
    if d[41-i]<0 and p+2**(40-i)<=y:
        s+="1"
        p+=2**(40-i)
    else:
        s+="0"
s=int(s,2)
k=0
for i in a:
    k+=i^s
print(k)

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

def main():
    N, K = map(int, input().split())
    A = np.array(list(map(int, input().split())))
    
    ans = 0
    B = np.zeros(40, dtype=int)
    
    for i in range(40):
        B[39-i] = np.count_nonzero(A%2)
        A //= 2
        
    k = 2**39
    x = 0
    for i in range(40):
        if B[i] > N-B[i]: ans += B[i]*k
        else:
            if x+k <= K: x += k; ans += (N-B[i])*k
            else: ans += B[i]*k
        k //= 2
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n,k = map(int,readline().split())
lst1 = list(map(int,readline().split()))

"""
lst1に関しての全ての1の出現回数を求め、
lst1の半分より(1の出現回数が多いなら)多いならkのその桁を0に、
少ないならkのその桁を1にすることによってfは最大化される。

ただし、kには制約があるので、上位桁を優先として、制約内に収まる答えを探す。
"""
k = bin(k)
k = k[2:]
lst2 = [0]*40

for i in lst1:
    for j in range(40):
        if i >> j & 1:
            lst2[j] += 1 
lst2.reverse()
lst2 = lst2[40-len(k):]
th = n//2 

free = 0 
res = 0
for i in range(len(k)):
    if not free:
        if k[i] == "1":
            if lst2[i] <= th:
                res += 1 << len(k)-1-i
            else:
                free = 1
    else:
        if lst2[i] < th:
                res += 1 << len(k)-1-i


ans = 0
for i in lst1:
    ans += i^res
print(ans)

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

def main():
    N,K = map(int,input().split())
    a = list(map(int,input().split()))
    M = max(max(a),K).bit_length()
    l = [0 for _ in range(M)]
    for num in a:
        for i in range(M):
            l[i] += num%2
            num //= 2

    use = 0
    for i in reversed(range(M)):
        if l[i] < -(-N//2):
            if use+2**i <= K:
                use += 2**i
    
    ans = 0        
    for num in a:
        ans += (num^use)
        
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict


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

d = defaultdict(int)

for a in A:
    for i in range(50):
        if a & (1 << i):
            d[i] += 1
dp = [[-1 for _ in range(2)] for _ in range(51)]
dp[0][0] = 0


for i in range(50):


    
    if K & (1 << (50-i-1)):
        digit = 1
    else:
        digit = 0

    
    use_1 = (N-d[50-i-1]) * (1 << (50-i-1))
    
    use_0 = d[50-i-1] * (1 << (50-i-1))

    if K < (1 << (50-i-1)):
        use_1 = 0

    """
    i-1桁までがKより小さい場合、0,1どちらも選択可能
    dp[i][1] == -1 だとそれは起こりえない
    """
    if dp[i][1] != -1:
        dp[i+1][1] =  dp[i][1] + max(use_0, use_1)

    """
    i-1桁まで同じで、i桁目でKより小さくなる場合（Kのi桁目が1で0を選択）
    ここでmax(dp[i+1][1], ～)にしてあげないと、上で決めたものが上書きされてしまう
    """
    if dp[i][0] != -1:
        if digit == 1:
            dp[i+1][1] = max(dp[i+1][1], dp[i][0] + use_0)

    """
    i-1桁まで同じで、i桁目でKとまた一致する場合

    """
    if dp[i][0] != -1:
        if digit == 1:
            dp[i+1][0] = dp[i][0] + use_1
        else:
            dp[i+1][0] = dp[i][0] + use_0

print(max(dp[-1]))

Solution (Python):
from collections import defaultdict


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

d = defaultdict(int)

for a in A:
    for i in range(50):
        if a & (1 << i):
            d[i] += 1
dp = [[-1 for _ in range(2)] for _ in range(51)]
dp[0][0] = 0


for i in range(50):


    
    if K & (1 << (50-i-1)):
        digit = 1
    else:
        digit = 0

    
    use_1 = (N-d[50-i-1]) * (1 << (50-i-1))
    
    use_0 = d[50-i-1] * (1 << (50-i-1))

    if K < (1 << (50-i-1)):
        use_1 = 0

    """
    i-1桁までがKより小さい場合、0,1どちらも選択可能
    dp[i][1] == -1 だとそれは起こりえない
    """
    if dp[i][1] != -1:
        dp[i+1][1] =  dp[i][1] + max(use_0, use_1)

    """
    i-1桁まで同じで、i桁目でKより小さくなる場合（Kのi桁目が1で0を選択）
    ここでmax(dp[i+1][1], ～)にしてあげないと、上で決めたものが上書きされてしまう
    """
    if dp[i][0] != -1:
        if digit == 1:
            dp[i+1][1] = max(dp[i+1][1], dp[i][0] + use_0)

    """
    i-1桁まで同じで、i桁目でKとまた一致する場合
    ここのmax~はいらないと思う
    """
    if dp[i][0] != -1:
        if digit == 1:
            dp[i+1][0] = max(dp[i+1][0], dp[i][0] + use_1)
        else:
            dp[i+1][0] = max(dp[i+1][0], dp[i][0] + use_0)

print(max(dp[-1]))

Solution (Python):
from collections import defaultdict


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

d = defaultdict(int)

for a in A:
    for i in range(50):
        if a & (1 << i):
            d[i] += 1
dp = [[-1 for _ in range(2)] for _ in range(51)]
dp[0][0] = 0


for i in range(50):


    
    if K & (1 << (50-i-1)):
        digit = 1
    else:
        digit = 0

    
    use_1 = (N-d[50-i-1]) * (1 << (50-i-1))
    
    use_0 = d[50-i-1] * (1 << (50-i-1))

    if K < (1 << (50-i-1)):
        use_1 = 0

    """
    i-1桁までがKより小さい場合、0,1どちらも選択可能
    dp[i][1] == -1 だとそれは起こりえない
    """
    if dp[i][1] != -1:
        dp[i+1][1] =  dp[i][1] + max(use_0, use_1)

    """
    i-1桁まで同じで、i桁目でKより小さくなる場合（Kのi桁目が1で0を選択）
    """
    if dp[i][0] != -1:
        if digit == 1:
            dp[i+1][1] = max(dp[i+1][1], dp[i][0] + use_0)

    """
    i-1桁まで同じで、i桁目でKとまた一致する場合
    """
    if dp[i][0] != -1:
        if digit == 1:
            dp[i+1][0] = max(dp[i+1][0], dp[i][0] + use_1)
        else:
            dp[i+1][0] = max(dp[i+1][0], dp[i][0] + use_0)

print(max(dp[-1]))

Solution (Python):
from collections import defaultdict


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

d = defaultdict(int)

for a in A:
    for i in range(50):
        if a & (1 << i):
            d[i] += 1
dp = [[-1 for _ in range(2)] for _ in range(51)]
dp[0][0] = 0


for i in range(50):


    
    if K & (1 << (50-i-1)):
        digit = 1
    else:
        digit = 0

    
    use_1 = (N-d[50-i-1]) * (1 << (50-i-1))
    
    use_0 = d[50-i-1] * (1 << (50-i-1))

    if K < (1 << (50-i-1)):
        use_1 = 0

    """
    i-1桁までがKより小さい場合、0,1どちらも選択可能
    dp[i][1] == -1 だとそれは起こりえない
    """
    if dp[i][1] != -1:
        dp[i+1][1] = max(dp[i+1][1], dp[i][1] + max(use_0, use_1))

    """
    i-1桁まで同じで、i桁目でKより小さくなる場合（Kのi桁目が1で0を選択）
    """
    if dp[i][0] != -1:
        if digit == 1:
            dp[i+1][1] = max(dp[i+1][1], dp[i][0] + use_0)

    """
    i-1桁まで同じで、i桁目でKとまた一致する場合
    """
    if dp[i][0] != -1:
        if digit == 1:
            dp[i+1][0] = max(dp[i+1][0], dp[i][0] + use_1)
        else:
            dp[i+1][0] = max(dp[i+1][0], dp[i][0] + use_0)

print(max(dp[-1]))

Solution (Python):

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


keta=50
L=[[N,0]]

for i in range(keta-1,-1,-1): 
    count=[ 0 for _ in range(2) ]
    for a in A:
        key=a>>i&1  
        count[key]+=1
    L.append(count)

T=[ float("-inf") for _ in range(keta+1) ]
F=[ float("-inf")  for _ in range(keta+1) ]
F[0]=0

for i in range(1,keta+1):
    bit=K>>(keta-i)&1
    if bit==1:
        F[i]=F[i-1]+2**(keta-i)*L[i][0] 
        
        T[i]=max( F[i-1]+2**(keta-i)*L[i][1],T[i-1]+2**(keta-i)*L[i][0],T[i-1]+2**(keta-i)*L[i][1] )
    else:
        F[i]=F[i-1]+2**(keta-i)*L[i][1] 
        T[i]=max( T[i-1]+2**(keta-i)*L[i][0],T[i-1]+2**(keta-i)*L[i][1] )   


print max(T[-1],F[-1])

Solution (Python):

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


keta=50
L=[[N,0]]

for i in range(keta-1,-1,-1): 
    count=[ 0 for _ in range(2) ]
    for a in A:
        key=a>>i&1  
        count[key]+=1
    L.append(count)

T=[ float("-inf") for _ in range(keta+1) ]
F=[ float("-inf")  for _ in range(keta+1) ]
F[0]=0

for i in range(1,keta+1):
    bit=K>>(keta-i)&1
    if bit==1:
        F[i]=F[i-1]+2**(keta-i)*L[i][0] 
        
        T[i]=max( F[i-1]+2**(keta-i)*L[i][1],T[i-1]+2**(keta-i)*L[i][0],T[i-1]+2**(keta-i)*L[i][1] )
    else:
        F[i]=F[i-1]+2**(keta-i)*L[i][1] 
        T[i]=max( T[i-1]+2**(keta-i)*L[i][0],T[i-1]+2**(keta-i)*L[i][1] )   


print max(T[-1],F[-1])

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

K += 1
binary_K = format(K, '041b')
ideal_x = ""
for i in reversed(range(41)):
    bit = 1 << i
    count = 0
    
    for a in A:
        if a & bit:
            count += 1
    if count > N - count:  
        ideal_x += "0"
    else:
        ideal_x += "1"



ans = 0
for i in range(41):
    if binary_K[i] == "0":
        continue
    x = binary_K[:i] + "0" + ideal_x[i+1:]
    x = int(x, 2)
    fx = 0
    for a in A:
        fx += a ^ x
    ans = max(ans, fx)
print(ans)

Solution (Python):

import sys


def solve(N: int, K: int, A: "List[int]"):
    dp = [[-1]*2 for _ in range(45)]
    dp[43][0] = 0
    for i in range(43,-1,-1):
        count = 0 
        for j in range(N):
            if (1 << i & A[j]):
                count += 1
        
        
        if dp[i+1][1] >= 0:
            dp[i][1] = max(dp[i+1][1] + max(count,N-count)*(1<<i),dp[i][1])

        if dp[i+1][0] >= 0:
            if K & 1<<i: 
                
                dp[i][0] = max(dp[i+1][0]+(N-count)*(1<<i),dp[i][0])
                
                dp[i][1] = max(dp[i+1][0] + count*(1<<i),dp[i][1])
            else: 
                
                dp[i][0] = max(dp[i+1][0] + count*(1<<i) ,dp[i][0])
    
    print(max(dp[0][0],dp[0][1]))
    return


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)]  
    solve(N, K, A)

if __name__ == '__main__':
    main()

Solution (Python):
n,k = map(int,input().split())
bitl = [0 for i in range(50)]
al = map(int,input().split())
ansl = [0 for i in range(50)]

for a in al:
  p = 0
  while a:
    bitl[p] += a % 2
    a //= 2
    p += 1
p=0
while k:
  ansl[p] = k % 2
  k //= 2
  p += 1

ans = 0
for i in range(50):
  tmp = 0
  if ansl[i] != 1:
    continue
  else:
    for j in range(i):
      tmp += 2 ** j * max(bitl[j], n-bitl[j])
    tmp +=2 ** i * bitl[i]
    for j in range(i+1, 50):
      if ansl[j] == 0:
        tmp += 2 ** j * bitl[j]
      else:
        tmp += 2 ** j * (n-bitl[j])
  ans = max(ans, tmp)
else:
  tmp = 0
  for j in range(0, 50):
    if ansl[j] == 0:
      tmp += 2 ** j * bitl[j]
    else:
      tmp += 2 ** j * (n - bitl[j])
  ans = max(ans, tmp)

print(ans)

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans,l=0,0
for i in range(40)[::-1]:
  b=1<<i
  c=sum(bool(x&b) for x in a)
  if l+b<=k and c<n-c:
    l+=b
    ans+=b*(n-c)
  else:
    ans+=b*c
print(ans)

Solution (Python):


N, K = map(int, input().split())
A = list(map(int, input().split()))
K += 1
K_bit = format(K, "b")

tmp = ""  
for i in reversed(range(len(K_bit))):
    
    bit = 1 << i
    count = 0
    for a in A:
        if a & bit:
            count += 1
    if count > N - count:
        tmp += "0"
    else:
        tmp += "1"

ans = 0
for i in range(len(K_bit)):
    bit = 1 << i
    if K_bit[i] == "1":  
        num = K_bit[:i] + "0" + tmp[i+1:]
        num = int(num, 2)
        fx = 0
        for a in A:
            fx += num ^ a
        ans = max(ans, fx)
    else:
        continue
print(ans)

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

tab = [] * 64
X_tmp = 1
for i in range(64):
    tab_tmp = 0
    for j, Aj in enumerate(A):
        tab_tmp += ((Aj >> i) & 0b1)
    tab.append(tab_tmp)

X_ans = 0
for i_inv in range(64):
    i = 63 - i_inv
    if X_ans + (1 << i) > K: continue
    elif tab[i] * 2 >= N: continue
    else:
        X_ans += (1 << i)



ans = 0
for Ai in A:
    ans += (Ai ^ X_ans)
print(ans)

Solution (Python):
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def h(m):
    sm = 0
    for j in range(m+1):
        sm += max(b[j],n-b[j]) * 2**j
    return sm

def g(k,m):
    if m<0:
        return 0
    if k<2**m:
        return 2**m * b[m] + g(k,m-1)
    return max(2**m * b[m] + h(m-1), \
               2**m * (n-b[m]) + g(k-2**m, m-1))

n,k = inm()
a = inl()
b = [0]*40
for i in range(n):
    for j in range(40):
        b[j] += (a[i]>>j)%2
print(g(k,39))

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

one_count = [0]*41

for a in alist:
    for i,b in enumerate(format(a,'b')[::-1]):
        one_count[i] += int(b)

x = 0
adj = 0
for i,count in enumerate(one_count[::-1]):
    tmp = (count < n/2) * (2**(40-i))
    if x + tmp <= k :
        x += tmp
        adj += (n-2*count) * tmp
print(sum(alist)+adj)

Solution (Python):
import sys
input=sys.stdin.readline
def main():
  n,k=map(int,input().split())
  a=list(map(int,input().split()))
  dp=[[-1]*(2) for i in range(51)]
  dp[0][0]=0
  maxdigit=50
  for i in range(maxdigit):
    mask=1<<(maxdigit-i-1)
    cnt=0
    for j in range(n):
      if mask&a[j]:
        cnt+=1
    cost0=mask*cnt
    cost1=mask*(n-cnt)
    if dp[i][1]!=-1:
      dp[i+1][1]=max(dp[i+1][1],dp[i][1]+max(cost0,cost1))
    if dp[i][0]!=-1:
      if k&mask:
        dp[i+1][0]=max(dp[i+1][0],dp[i][0]+cost1)
        dp[i+1][1]=max(dp[i+1][1],dp[i][0]+cost0)
      else:
        dp[i+1][0]=max(dp[i+1][0],dp[i][0]+cost0)
  return print(max(dp[maxdigit][0],dp[maxdigit][1]))
if __name__=='__main__':
  main()

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

data=[0 for i in range(45)]
for a in A:
    b=list(bin(a)[2:])
    b.reverse()
    for i in range(len(b)):
        if b[i]=="1":
            data[i]+=1
numlst=[]
bink=list(bin(K)[2:])
bink.reverse()
K_nagasa=len(bink)
num1=0

for k in range(len(data)-1,-1,-1):

    if K_nagasa>k and bink[k]=="1":
        
        num=num1+data[k]*(2**k)
        for i in range(k):
            num+=max(N-data[i],data[i])*(2**i)
        numlst.append(num)
        num=num1+max(N-data[k],data[k])*(2**k)
        num1+=(N-data[k])*(2**k)
        k-=1

        if k>=0:
            while k>0 and bink[k]!="1":
                num+=data[k]*(2**k)
                k-=1
            num+=data[k]*(2**k)
            if bink[k]!="1":
                for i in range(k):
                    num+=max(N-data[i],data[i])*(2**i)
        numlst.append(num)


    else:
        num1+=data[k]*(2**k)
    numlst.append(num1)
print(max(numlst))

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

li = [0 for i in range(40)]

for i in range(N):
    j = 0
    while((A[i]>>j) > 0):
        if (A[i]>>j)&1:
            li[j] += 1
        j += 1

mm = 0
for j in range(39,-1,-1):
    if li[j] <= N-li[j]:
        if (mm + (1<<j)) <= K:
            mm += 1<<j

ans = 0
for n in range(N):
    ans += mm^A[n]

print(ans)

Solution (Python):
n, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
b = 2**40

dp = [0, 0]

flag = True
while b>0:
    dp2 = dp[:]
    c = 0
    d = 0
    for i in a:
        if (i & b) == 0:
            c += 1
        else:
            d += 1
    if (k & b) == 0:
        if not flag:
            dp[0] = dp2[0]+max(c, d) * b
            dp[1] += d * b
        else:
            dp[1] += d * b
    else:
        if not flag:
            dp[0] = max(dp2[0]+max(c, d) * b, dp2[1]+d * b)
            dp[1] += c * b
        else:
            dp[0] += d*b
            dp[1] += c * b
            flag = False
        
    b //= 2

print(max(dp))

Solution (Python):
n,k = map(int, input().split( ))
a = list(map(int, input().split( )))
l = max(max(a),k).bit_length()
x = 0
ans = 0
flag = False
for i in range(l-1,-1,-1):
    cnt = 0
    
    for j in range(n):
        cnt += a[j]>>i&1
    if (k>>i&1 or flag) and cnt<n-cnt:
        x += 1<<i
        ans += (n-cnt)*(1<<i)
    else:
        ans += cnt*(1<<i)
    if (k>>i)>(x>>i):
        flag = True
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

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

nK=len(bin(K))-2
nA=len(bin(max(A)))-2
n=max(nK,nA)

p=[1]*(n+1)
for i in range(n):
    p[i+1]=p[i]*2

XX=[0]*n
temp=0


for i in range(nK-1,-1,-1):
    cnt=0
    for j in range(N):
        if A[j]&p[i]==p[i]:
            cnt+=1
    if cnt<N-cnt:
        if temp+p[i]<=K:
            XX[i]=1
            temp+=p[i]
    
ans=0
for i in range(N):
    ans+=temp^A[i]
    
print(ans)

Solution (Python):
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

n,k=map(int,input().split())
a=list(map(int,input().split()))
m=0
if k==0:
    m=int(math.log2(1)+1)
else:
    m=int(math.log2(k)+1)
lst=[0]*m
for i in range(n):
    for j in range(m):
        if a[i]&(1<<j):
            lst[j]+=1


ans=0
ans2=0
for i in range(m):
    if lst[m-i-1]<=n/2 and ans+pow(2,m-i-1)<=k:
        ans+=pow(2,m-i-1)


for i in range(n):
    ans2+=ans^a[i]

print(ans2)

Solution (Python):
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

n,k=map(int,input().split())
a=list(map(int,input().split()))
m=0
if k==0:
    m=1
else:
    m=int(math.log2(k)+1)
lst=[0]*m
for i in range(n):
    for j in range(m):
        if a[i]&(1<<j):
            lst[j]+=1


ans=0
ans2=0
for i in range(m):
    if lst[m-i-1]<=n/2 and ans+pow(2,m-i-1)<=k:
        ans+=pow(2,m-i-1)


for i in range(n):
    ans2+=ans^a[i]

print(ans2)

Solution (Python):
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

n,k=map(int,input().split())
a=list(map(int,input().split()))
m=0
if k==0:
    m=int(math.log2(1)+1)
else:
    m=int(math.log2(k)+1)
lst=[0]*m
for i in range(n):
    for j in range(m):
        if a[i]&(1<<j):
            lst[j]+=1


ans=0
ans2=0
for i in range(m):
    if lst[m-i-1]<=n/2 and ans+pow(2,m-i-1)<=k:
        ans+=pow(2,m-i-1)


for i in range(n):
    ans2+=ans^a[i]

print(ans2)

Solution (Python):
MAX_DIGIT = 50
SMALL = 1
EQUAL = 0

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

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

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

    
    cost0 = mask * num  
    cost1 = mask * (N - num)  

    
    if dp[d][SMALL] != -1:
        
        dp[d+1][SMALL] = max(dp[d+1][SMALL], dp[d][SMALL] + max(cost0, cost1))

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

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


ans = max(dp[MAX_DIGIT][EQUAL], dp[MAX_DIGIT][SMALL])
print(ans)

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

keta = len(str(format(K, 'b')))
T = [0]*keta
for a in A:
    for i in range(keta):
        if (((1<<i)&(a))>>i) == 1:
            T[i] += 1

tmp = ''
for t in T:
    if t > N//2:
        tmp += '0'
    else:
        tmp += '1'
XX = list(tmp[::-1])
KK = str(format(K, 'b'))
if int(tmp[::-1], 2) > K:
    for i in range(len(XX)):
        if (XX[i] != KK[i]) and XX[i] == '1':
            XX[i] = '0'
        elif (XX[i] != KK[i]) and XX[i] == '0':
            break

X = int(''.join(XX), 2)
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()))

L = [0] * 50

for a in A:
    i = 0
    while a > 0:
        L[i] += a & 1
        i += 1
        a >>= 1

X = 0
ans = 0
for i in range(49, -1, -1):
    if L[i] < (N + 2 - 1) // 2 and X + (1 << i) <= K:
        num = N - L[i]
        bit = 1
    else:
        num = L[i]
        bit = 0
    ans += (1 << i) * num
    X += (bit << i)

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
a = list(map(int, input().split()))
t = [0] * 41
x = 0
res = 0
for i in range(N):
  for j in range(41):
    t[j] += (a[i] & (1 << j)) > 0

tt = [[0] * 2 for _ in range(41)]
for i in range(41):
  tt[i][0] = t[i] * (1 << i)
  tt[i][1] = (N - t[i]) * (1 << i)
for i in range(40, -1, -1):
  if x + (1 << i) > K:
    res += tt[i][0]
    continue
  if tt[i][0] >= tt[i][1]:
    res += tt[i][0]
  else:
    res += tt[i][1]
    x += 1 << i
print(res)

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

bit = [0 for _ in range(40)]

for i in range(N):
    s = format(A[i],'040b')
    for j in range(40):
        bit[j] += int(s[j])
        
x = 0
ans = 0

for j in range(40):
    if N-bit[j] > bit[j] and 2**(39-j)+x <= K:
        x += 2**(39-j)
    
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()))



from math import log2
num = int(log2(10**12) + 1)
box = [0] * (num + 1)
for i in a:
  l = bin(i)[2:][::-1]
  for itr, val in enumerate(l):
    box[itr] += int(val)

X = 0
for itr, val in enumerate(box[::-1]):
  if val <= n // 2 and X + 2 ** (num - itr) <= k:
    X += 2 ** (num - itr)

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

Solution (Python):
import sys
from math import log2, floor

n, k, *A = map(int, sys.stdin.read().split())

def main():
    if k == 0:
        return sum(A)

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

    bl = [bits[i] < n / 2 for i in range(40)]

    k_bit = [k >> i & 1 for i in range(40)]
    i = floor(log2(k))
    while True:
        tmp_x = 2 ** i - 1
        x_bit = [tmp_x >> j & 1 for j in range(40)]
        res1 = 0
        res2 = 0
        for j in range(i+1):
            if k_bit[j] & bl[j]:
                res1 += 2 ** j * (n - bits[j])
            else:
                res1 += 2 ** j * bits[j]
            
            if x_bit[j] & bl[j]:
                res2 += 2 ** j * (n - bits[j])
            else:
                res2 += 2 ** j * bits[j]
            
        if res2 > res1:
            for j in range(i):
                k_bit[j] |= 1
            k_bit[i] = 0
            break

        for j in range(i-1, -1, -1):
            if k_bit[j] == 1:
                i = j
                break
        else:
            break

    res = 0
    for i in range(40):
        if bl[i] & k_bit[i]:
            res += 2 ** i * (n - bits[i])
        else:
            res += 2 ** i * bits[i]
    
    return res

if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
from collections import Counter,defaultdict,deque
import sys
from itertools import permutations, combinations
from heapq import heappop, heappush

sys.setrecursionlimit(10**8)

    
def inp(): 
    return int(input())
def inpm(): 
    return map(int,input().split())
def inpl(): 
    return list(map(int, input().split()))
def inpls(): 
    return list(input().split())
def inplm(n): 
    return list(int(input()) for _ in range(n))
def inpll(n): 
    return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    n,k = inpm()
    a = inpl()
    x = [0 for _ in range(41)]
    y = [0 for _ in range(41)]
    index = 0
    while k > 0:
        x[index] += k%2
        k //= 2
        index += 1
    for i in range(n):
        index = 0
        while a[i] > 0:
            y[index] += a[i]%2
            a[i] //= 2
            index += 1
    ans = 0
    key1 = 0
    key2 = 0
    for i in range(40,-1,-1):
        flag = (y[i]>=(n/2))
        if x[i]>0 or y[i]>0:
            key2 = 1
        if x[i] == 1 and flag and key2 and (not key1):
            key1 = True
            ans += pow(2,i)*y[i]
        elif key2:
            if flag or (x[i] == 0 and (not key1)):
                ans += pow(2,i)*y[i]
            else:
                ans += pow(2,i)*(n-y[i])
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):

n, k = map(int, input().split())
k = ['0'] * (42 - len(list(bin(k)[2:]))) + list(bin(k)[2:])
a = list(map(int, input().split()))

b = [[0] for _ in range(n)]
for i in range(n):
    b[i] = ['0'] * (42 - len(list(bin(a[i])[2:]))) + list(bin(a[i])[2:])

count = [[0, 0] for _ in range(42)]
for j in range(42):
    c_0, c_1 = 0, 0
    for i in range(n):
        if b[i][j] == '0':
            c_0 += 1
        else:
            c_1 += 1
    count[j] = c_0, c_1
        
ans = []
for i in range(42):
    if count[i][1] >= count[i][0]:
        ans.append('0')
    else:
        ans.append('1')

flag = False
for i in range(42):
    if ans[i] == '1' and k[i] == '0':
        ans[i] = '0'
    elif ans[i] == '0' and k[i] == '1':
        flag = True
    
    if flag:
        break

tmp = 0
ans = ans[::-1]
for i in range(42):
    if ans[i] == '1':
        tmp += 2**i

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

Solution (Python):

n, k = map(int, input().split())
k = ['0'] * (42 - len(list(bin(k)[2:]))) + list(bin(k)[2:])
a = list(map(int, input().split()))

b = [[0] for _ in range(n)]
for i in range(n):
    b[i] = ['0'] * (42 - len(list(bin(a[i])[2:]))) + list(bin(a[i])[2:])

count = [[0, 0] for _ in range(42)]
for j in range(42):
    c_0, c_1 = 0, 0
    for i in range(n):
        if b[i][j] == '0':
            c_0 += 1
        else:
            c_1 += 1
    count[j] = c_0, c_1
        
ans = []
for i in range(42):
    if count[i][1] >= count[i][0]:
        ans.append('0')
    else:
        ans.append('1')

flag = False
for i in range(42):
    if ans[i] == '1' and k[i] == '0':
        ans[i] = '0'
    elif ans[i] == '0' and k[i] == '1':
        flag = True
    
    if flag:
        break

tmp = 0
ans = ans[::-1]
for i in range(42):
    if ans[i] == '1':
        tmp += 2**i

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

Solution (Python):
N,K = map(int, input().split())
a = list(map(int, input().split()))
Kbin = bin(K)[2:]
Kbin = Kbin.zfill(43)
s = len(str(K))
sbin = len(Kbin)
bintbl1 = [0 for i in range(sbin)]
bintbl0 = [0 for i in range(sbin)]
for i in range(N):
  abin = bin(a[i])[2:]
  abin = abin.zfill(sbin)
  for j in range(sbin):
    if abin[j] == "1":
      bintbl1[j] += 1
    else:
      bintbl0[j] += 1
DP = [[[0 for i in range(2)] for j in range(2)] for k in range(sbin)]
for i in range(1,sbin):
  if Kbin[i] == "1":
    if sbin-len(bin(K)[2:]) == i:
      DP[i][1][0] = max(DP[i-1][0][0],DP[i-1][1][0]) + bintbl0[i]*2**(sbin-i-1)
      DP[i][0][1] = max(DP[i-1][0][0],DP[i-1][0][1],DP[i-1][1][1],DP[i-1][1][0]) + (bintbl1[i]*2**(sbin-i-1))
    else:
      DP[i][1][0] = max(DP[i-1][0][0],DP[i-1][1][0]) + bintbl0[i]*2**(sbin-i-1)
      DP[i][1][1] = max(DP[i-1][0][1],DP[i-1][1][1]) + bintbl0[i]*2**(sbin-i-1)
      DP[i][0][0] = 0
      DP[i][0][1] = max(DP[i-1][0][0],DP[i-1][0][1],DP[i-1][1][1],DP[i-1][1][0]) + (bintbl1[i]*2**(sbin-i-1))
  if Kbin[i] == "0":
    if sbin-len(bin(K)[2:])>i:
      DP[i][0][0] = max(DP[i-1][0][0],DP[i-1][1][0]) + bintbl1[i]*2**(sbin-i-1)
    else:
      DP[i][1][0] = 0
      DP[i][1][1] = max(DP[i-1][0][1],DP[i-1][1][1]) + bintbl0[i]*2**(sbin-i-1)
      DP[i][0][0] = max(DP[i-1][0][0],DP[i-1][1][0]) + bintbl1[i]*2**(sbin-i-1)
      DP[i][0][1] = max(DP[i-1][0][1],DP[i-1][1][1]) + bintbl1[i]*2**(sbin-i-1)
print(max(DP[sbin-1][0][0],DP[sbin-1][0][1],DP[sbin-1][1][0],DP[sbin-1][1][1]))

Solution (Python):
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines





import numpy as np

def main():
	N, K,*A = map(int, read().split())
	a = np.array(A,dtype=np.int64)
	ans = 0
	for i in range(50, -1, -1):
		s = np.sum((a >> i) & 1)
		
		if N - s > s:
			ans += 1<<i
		if ans > K:
			ans -= 1<<i
		
	print(np.sum(ans ^ a))


if __name__ == "__main__":
	main()

Solution (Python):

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

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

lis = [0] * 41

for i in range(N):
    for j in range(41):
        if A[i] & (2**j) != 0:
            lis[j] += 1


now = 0
ans = 0


for i in range(41):

    i = 40-i

    if lis[i] >= N / 2:
        ans += (2**i)*lis[i]

    else:
        if now + 2**i <= K:
            now += 2**i
            ans += (2**i) * (N - lis[i])
        else:
            ans += (2**i) * lis[i]

    

print (ans)

Solution (Python):
import numpy as np
from functools import lru_cache

N,K = map(int,input().split())
A = np.array(input().split(),dtype=np.int64)

bit_cnt = [((A>>k)&1).sum() for k in range(50)]

@lru_cache(maxsize = None)
def F(K,k = 49):
  
  if k == -1:
    return 0
  bit = 1<<k
  
  x = 0
  if K >= bit:
    x = ((N-bit_cnt[k])<<k) + F(K-bit,k-1)
  
  y = (bit_cnt[k]<<k) + F(min(K,bit-1),k-1)
  return max(x,y)

answer = F(K)
print(answer)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
ans, k = 0, 0
for i in range(40)[::-1]:
    b = 1 << i
    c = sum(bool(a & b) for a in A)
    if k + b <= K and c < N - c:
        k += b
        ans += b * (N - c)
    else:
        ans +=  b * c
print(ans)

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

Am=max(A)

lAm=len(bin(Am))-2

k=bin(K)[2:]
lK=len(bin(K))-2




ANS=[[-1 for i in range(2)] for j in range(41)]




for i in range(N):
  X=bin(A[i])[2:]
  for j in range(max(lAm,lK)-len(X)):
    X="0"+X
  bA.append(X)

for j in range(max(lAm,lK)-len(k)):
  k="0"+k




def opt(a,index,counter):
  if ANS[index][counter]==-1:
    if index<a:
      if counter==1:
        z=0
        o=0
        for i in range(N):
          if bA[i][index]=="1":
            o+=1
          else:
            z+=1

        temp=k[index]
        if temp=="1":
          t1=o*pow(2,a-index-1) + opt(a,index+1,0)

          t2=z*pow(2,a-index-1) + opt(a,index+1,1)
          ANS[index][counter]=max(t1,t2)
        else:
          ANS[index][counter]=o*pow(2,a-index-1) + opt(a,index+1,1)
      elif counter==0:
        z=0
        o=0
        for i in range(N):
          if bA[i][index]=="1":
            o+=1
          else:
            z+=1
        ANS[index][counter]=max(o,z)*pow(2,a-index-1) + opt(a,index+1,0)
    else:
      ANS[index][counter]=0
  
  return ANS[index][counter]


print(opt(max(lAm,lK),0,1))