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

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


for i in range(len(a)):
    a[i] = '{:040b}'.format(a[i])
p = len(bin(k))-2
k = '{:040b}'.format(k)
t = True
ans = 0
for i in range(0,40):
    num_1 = 0
    num_0 = 0
    if t:
        if k[i] == '1':
            for j in range(n):
                if a[j][i] == '1':
                    num_1 += 1
                elif a[j][i] == '0':
                    num_0 += 1
            if num_0 > num_1:
                num = num_0
                ans += (2**(39-i))*num
            else:
                t = False
                num = num_1
                ans += (2**(39-i))*num
        elif k[i] == '0':
            for j in range(n):
                if a[j][i] == '1':
                    num_1 += 1
                elif a[j][i] == '0':
                    num_0 += 1
            num = num_1
            ans += (2**(39-i))*num
    else:
        for j in range(n):
            if a[j][i] == '1':
                num_1 += 1
            elif a[j][i] == '0':
                num_0 += 1
        if num_0 > num_1:
            num = num_0
            ans += (2**(39-i))*num
        else:
            num = num_1
            ans += (2**(39-i))*num
print(ans)

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


for i in range(len(a)):
    a[i] = '{:040b}'.format(a[i])
p = len(bin(k))-2
k = '{:040b}'.format(k)
ans = 0
for i in range(0,40-p):
    num_1 = 0
    num_0 = 0
    for j in range(n):
        if a[j][i] == '1':
            num_1 += 1
        elif a[j][i] == '0':
            num_0 += 1
    num = num_1
    ans += (2**(39-i))*num

t = True
for i in range(40-p,40):
    num_1 = 0
    num_0 = 0
    if t:
        if k[i] == '1':
            for j in range(n):
                if a[j][i] == '1':
                    num_1 += 1
                elif a[j][i] == '0':
                    num_0 += 1
            if num_0 > num_1:
                num = num_0
                ans += (2**(39-i))*num
            else:
                t = False
                num = num_1
                ans += (2**(39-i))*num
        elif k[i] == '0':
            for j in range(n):
                if a[j][i] == '1':
                    num_1 += 1
                elif a[j][i] == '0':
                    num_0 += 1
            num = num_1
            ans += (2**(39-i))*num
    else:
        for j in range(n):
            if a[j][i] == '1':
                num_1 += 1
            elif a[j][i] == '0':
                num_0 += 1
        if num_0 > num_1:
            num = num_0
            ans += (2**(39-i))*num
        else:
            num = num_1
            ans += (2**(39-i))*num
print(ans)

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

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

X = 0
for i in range(40, -1, -1):
  if bcs[i] >= N - bcs[i]:
    continue  
  t = 1 << i
  if X + t <= K:
    X += t

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

Solution (Python):
n,k=map(int,input().split())
ans=0 
curr=0 
l=[int(i) for i in input().split()]
for i in range(39,-1,-1):
    c=0 
    for j in range(n):
        if l[j]&(1<<i):
            c+=1 
    a=c 
    b=n-c 
    if b>a:
        if curr+(1<<i)<=k:
            curr+=(1<<i)
print(sum(i^curr for i in l))

Solution (Python):
import sys
import copy


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, k = list(map(int, readline().split()))
    a = list(map(int, readline().split()))
    ls = [0] * 50
    for v in a:
        s = bin(v)[2:]
        for i in range(len(s)):
            if s[-i-1] == "1":
                ls[i] += 1
    ans = ["0"] * 50
    for i in range(len(ls)):
        if ls[-i-1] <= n // 2:
            ans[i] = "1"
            t = copy.deepcopy(ans)
            if k < int("".join(t), 2):
                ans[i] = "0"
    t = 0
    for v in a:
        t += int("".join(ans), 2) ^ v
    print(t)


if __name__ == '__main__':
    solve()

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
lk=len(bin(K))-2
C=[0]*lk
for j in range(N):
  a=A[j]
  for i in range(lk):
    if a%2==1:
      C[i]+=1
    a=(a-a%2)//2

X="0b"
for i in reversed(range(lk)):
  if C[i]>=N-C[i]:
    X+="0"
  else:
    X+="1"
    
if int(X,0)<=K:
  X=int(X,0)
  ans=0
  for i in range(N):
    ans+=X^A[i]
  print(ans)
else:
  ans=-1
  for i in range(2,lk+2):
    x=int(bin(K)[:i]+"0"+X[i+1:],0)
    if x<=K:
      a=0
      for i in range(N):
        a+=x^A[i]
      ans=max(ans,a)
  print(ans)

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
lk=len(bin(K))-2
C=[0]*lk
for j in range(N):
  a=A[j]
  for i in range(lk):
    if a%2==1:
      C[i]+=1
    a=(a-a%2)//2

X="0b"
for i in reversed(range(lk)):
  if C[i]>=N-C[i]:
    X+="0"
  else:
    X+="1"
    
if int(X,0)<=K:
  X=int(X,0)
  ans=0
  for i in range(N):
    ans+=X^A[i]
  print(ans)
else:
  ans=-1
  for i in range(2,lk+2):
    x=int(bin(K)[:i]+"0"+X[i+1:],0)
    if x<=K:
      a=0
      for i in range(N):
        a+=x^A[i]
      ans=max(ans,a)
  print(ans)

Solution (Python):

import sys

def solve(N: int, K: int, A: "List[int]"):
    ans = 0
    max_bit = 40
    for i in range(max_bit+1):
        t = 2**(max_bit-i)
        count = len([1 for a in A if a&t > 0])
        if t <= K and count < N / 2:
            count = N - count
            K -= t
        ans += count * t
    print(ans)

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())
A = list(map(int, input().split()))
M = int(max(max(A), K)).bit_length()

maxVal = [0] * M  

for digit in range(M):
    cnt = 0
    mask = (1 << digit)
    for a in A:
        if (mask & a) > 0:
            cnt += 1
    cnt = max(cnt, N - cnt)
    maxVal[digit] = cnt * mask
    if digit > 0:
        maxVal[digit] += maxVal[digit - 1]

upperValK = [0] * (M + 1)

for digit in range(M)[:: -1]:
    mask = (1 << digit)
    maskedK = (K & mask)
    cnt = 0
    for a in A:
        if (a & mask) != maskedK:
            cnt += mask
    upperValK[digit] = cnt + upperValK[digit + 1]

ans = upperValK[0]
for mid in range(M):
    mask = (1 << mid)
    if not (mask & K) > 0:
        continue

    cnt = upperValK[mid + 1]
    for a in A:
        if (a & mask) > 0:
            cnt += mask
    if mid > 0:
        cnt += maxVal[mid - 1]
    ans = max(ans, cnt)

print(ans)

Solution (Python):
N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
MAX_DIGIT = 50
dp = [[-1, -1] for _ in range(MAX_DIGIT+1)]
dp[MAX_DIGIT][0] = 0


for d in range(MAX_DIGIT-1, -1, -1):
    
    cnt = sum([(a>>d)%2 for a in A])
    c0 = cnt << d
    c1 = (N - cnt) << d
    
    if (dp[d+1][1] != -1):
        dp[d][1] = max(dp[d][1], dp[d+1][1] + max(c0, c1))
    if (dp[d+1][0] != -1 and (K>>d)%2 == 1):  
        dp[d][1] = max(dp[d][1], dp[d+1][0] + c0)
    if (dp[d+1][0] != -1):
        if (K>>d)%2 == 1:
            dp[d][0] = max(dp[d][0], dp[d+1][0] + c1)
        else:
            dp[d][0] = max(dp[d][0], dp[d+1][0] + c0)
    
print(max(dp[0][0], dp[0][1]))

Solution (Python):


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

count_1_per_bit = [0] * (len(bin(K)) - 2)
for a in A:
    for k_digit in range((len(bin(K)) - 2)):
        if a & (1 << k_digit):
            count_1_per_bit[k_digit] += 1
            
optimal_x = 0
for k_digit in reversed(range((len(bin(K)) - 2))):
    if optimal_x + (1 << k_digit) <= K and count_1_per_bit[k_digit] <= N//2:
        optimal_x += (1 << k_digit)

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

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

N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)

bit_cnt = [((A >> i) & 1).sum() for i in range(40)]
bit_cnt = [0 if i > N - i else 1 for i in bit_cnt]

K_2 = format(K, 'b')
k = len(K_2)
X = []
if sum([2 ** i for i in range(k) if bit_cnt[i] == 1]) > K:
    for i in range(k - 1, -1, -1):
        if int(K_2[-i - 1]) < bit_cnt[i]:
            bit_cnt[i] = 0
            X.append(sum([2 ** i for i in range(k) if bit_cnt[i] == 1]))
else:
    X.append(sum([2 ** i for i in range(k) if bit_cnt[i] == 1]))

answer = [(i ^ A).sum() for i in X if i <= K]
print(max(answer))

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

N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)
a = (A ^ K).sum()

bit_cnt = [((A >> i) & 1).sum() for i in range(40)]
bit_cnt = [0 if i > N - i else 1 for i in bit_cnt]

K = format(K, 'b')
k = len(K)
X = []
if sum([2 ** i for i in range(k) if bit_cnt[i] == 1]) > int(K, 2):
    for i in range(k - 1, -1, -1):
        if int(K[-i - 1]) < bit_cnt[i]:
            bit_cnt[i] = 0
            X.append(sum([2 ** i for i in range(k) if bit_cnt[i] == 1]))
    X = [i for i in X if i <= int(K, 2)]
else:
    X.append(sum([2 ** i for i in range(k) if bit_cnt[i] == 1]))

answer = 0
for i in X:
    answer = max(answer, (i ^ A).sum())
print(answer)

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

M = len(bin(K)) - 2
one = [0] * M
for i in range(N) :
    for j in range(M) :
        one[j] += (A[i] >> j) & 1 

X = 0
for i in range(M - 1, -1, -1) :
    X *= 2
    if N - one[i] > one[i] :
        X += 1
        
for i in range(M - 1, -1, -1) :
    a = (X >> i) & 1
    b = (K >> i) & 1
    if a == 0 and b == 1 :
        break
    if a == 1 and b == 0 :
        X ^= (1 << i)
        
ret = 0
for i in range(N) :
    ret += A[i] ^ X
print(ret)

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

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

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

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

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from itertools import product
    n,k=map(int,input().split())
    cnt=[0]*40
    for a in map(int,input().split()):
        for d in range(40):
            cnt[d]+=(a>>d)&1
    dp=[0,-INF]
    for d in range(39,-1,-1):
        kb=(k>>d)&1
        newdp=[0,-INF]
        for lt,x in product(range(2),repeat=2):
            nlt=lt
            if(lt==0 and x>kb): continue
            if(x<kb): nlt=1
            newdp[nlt]=max(newdp[nlt],dp[lt]+(n-cnt[d] if(x) else cnt[d])*(1<<d))
        dp=newdp
    print(max(dp))
resolve()

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
l=len(bin(max(max(a),k)))-2
b=[bin(a[i])[2:].zfill(l)for i in range(n)]
s=bin(k)[2:].zfill(l)
x=""
f=True
for i in range(l):
  if f and s[i]=="0":x+="0";continue
  z=o=0
  for j in b:
    if j[i]=="0":z+=1
    else:o+=1
  if o<z:t="1"
  else:t="0"
  if s[i]+t=="10":f=False
  x+=t
x=int(x,2)
ans=0
for i in a:ans+=i^x
print(ans)

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

x = 0
for bit in range(45,-1,-1):
    stand = 0
    for i in a:
        if i>>bit&1:
            stand += 1
    if stand*2 < n and x + 2**bit <= k:
        x += 2**bit

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

print(fx)

Solution (Python):
import numpy as np

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

max_len = max(len(bin(K)[2:]), len(bin(A.max())[2:]))
bit_cnt = [((A>>k)&1).sum() for k in range(max_len)]

x = 0
for i in range(max_len-1, -1, -1):
    if x+2**i <= K and bit_cnt[i] < (N+1)//2:
        x += 2**i

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

Solution (Python):
import numpy as np

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

max_len = max(len(bin(K)[2:]), len(bin(max(A))[2:]))
bit_cnt = [((A>>k)&1).sum() for k in range(max_len)]

x = 0
for i in range(max_len-1, -1, -1):
    if x+2**i <= K and bit_cnt[i] < (N+1)//2:
        x += 2**i

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

Solution (Python):
inf = float('inf')

SMALLER = 0
TBD = 1

n, k = map(int, input().split())
a = tuple(map(int, input().split()))
b = [0] * 50  

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

dp = [[-inf] * 2 for _ in range(50 + 1)]
dp[50][TBD] = 0

for j in reversed(range(50)):
    if (k >> j) & 1 == 1:
        
        dp[j][TBD] = dp[j + 1][TBD] + ((n - b[j]) << j)
        dp[j][SMALLER] = max(
            dp[j + 1][TBD] + (b[j] << j),
            dp[j + 1][SMALLER] + (max(n - b[j], b[j]) << j)
        )
    else:
        
        dp[j][TBD] = dp[j + 1][TBD] + (b[j] << j)
        dp[j][SMALLER] = dp[j + 1][SMALLER] + (max(n - b[j], b[j]) << j)

print(max(dp[0]))

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

    ctr = 0
    for j in range(n):
        if (a[j]>>(41-i))&1 == 1:
            ctr += 1

    if ctr >= n-ctr:
        dp[i][0] = dp[i-1][0] + ctr*(2**(41-i))
        if (k >> (41-i))&1 == 1:
            dp[i][1] = 1
    else:
        if dp[i][1] == 1:
            dp[i][0] = dp[i-1][0]+(n-ctr)*(2**(41-i))
        else:
            if (k >> (41-i))&1 == 1:
                dp[i][0] = dp[i-1][0]+(n-ctr)*(2**(41-i))
            else:
                dp[i][0] = dp[i-1][0] + ctr*(2**(41-i))

print(dp[41][0])

Solution (Python):
n,k=map(int,input().split())
k2=format(k+1,"0%ib"%40)
lists=list(map(int,input().split()))
countlist=[0]*40
for j in lists:
    c=format(j,"0%ib"%40)
    for i in range(40):
        if c[i]=="1":
            countlist[i]+=1

emptylist=[]
for i in range(40):
    if k2[i]=="1":
        emptylist.append(i)
if k>=1:
    ans=0
    for i in emptylist:
        subing=0
        for j in range(40):
            if j<i:
                if k2[j]=="1":
                    subing+=(2**(39-j))*(n-countlist[j])
                elif k2[j]=="0":
                    subing+=(2**(39-j))*countlist[j]
            if j==i:
                subing+=(2**(39-i))*countlist[i]
            
            if j>i:
                subing+=(2**(39-j))*max(countlist[j],n-countlist[j])
        ans=max(ans,subing)
    print(ans)
elif k==0:
    ans=0
    for i in range(40):
        ans+=(2**(39-i))*countlist[i]
    print(ans)

Solution (Python):

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


flag=[0]*(40)
for u in a:
    for j in range(40):
        if (u>>j)&1==1:
            flag[j]+=1
            

m=0
M=0
l=0
L=0
for i in range(40):
    if (k>>i)&1==1:
        if n>2*flag[i]:
            if M>L+(2**i)*(n-2*flag[i]):
                L=M
                l=m
            else:
                L+=(2**i)*(n-2*flag[i])
                l+=2**i
        else:
            L=m
            l=m
    if n>2*flag[i]:
        M+=(2**i)*(n-2*flag[i])
        m+=2**i

ans=0
for u in a:
    ans+=(u^l)

print(ans)

Solution (Python):

n,k=map(int,input().split())
a=list(map(int,input().split()))
data0=[0]*40
data1=[0]*40
for u in a:
    for j in range(40):
        if (u>>j)&1==1:
            data1[j]+=1
        else:
            data0[j]+=1
data=[]
for i in range(40):
    if data0[i]-data1[i]>0:
        data.append([(data0[i]-data1[i])*(2**i),i])
data.sort(reverse=True)
lst=[]
for i in range(40):
    if data1[i]<data0[i]:
        lst.append(i)
m=len(lst)
dp=[[]]
x=0
for h in data:
    i=h[0]
    j=h[1]
    if x+2**j<=k:
        x+=2**j
ans=0
for u in a:
    ans+=x^u
print(ans)

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

max_len = max(len(bin(K)[2:]),len(bin(max(A))[2:]))
one = [0]*max_len
for a in A:
    for i,b in enumerate(bin(a)[2:].zfill(max_len)):
        if b == "1":
            one[i] += 1
one = one[::-1]

x = 0
for i in range(max_len-1,-1,-1):
    if x+2**i <= K and one[i] < (N+1)//2:
        x += 2**i

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

max_len = max(len(bin(K)[2:]),len(bin(max(A))[2:]))
one = [0]*max_len
for a in A:
    for i,b in enumerate(bin(a)[2:].zfill(max_len)):
        if b == "1":
            one[i] += 1
one = one[::-1]

x = 0
for i in range(max_len-1,-1,-1):
    if x+2**i <= K and one[i] < (N+1)//2:
        x += 2**i

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

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.buffer.readline().rstrip()
def resolve():
    n,k=map(int,input().split())
    m=k.bit_length()
    A=list(map(int,input().split()))
    flag=False 
    x=0
    for d in range(m-1,-1,-1):
        d_sum=sum((a>>d)&1 for a in A)
        if(d_sum<=(n//2)): 
            if(flag or ((k>>d)&1==1)):
                x+=(1<<d)
        else: 
            if((k>>d)&1==1):
                flag=True
    print(sum(a^x for a in A))
resolve()

Solution (Python):
from sys import stdin

N, K = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]


def to_bin(n):
    return bin(n)[2:]


cnt = [0] * 40
for a in A:
    b = to_bin(a)
    b = b[::-1]
    for i in range(len(b)):
        if b[i] == '1':
            cnt[i] += 1

ans = 0
cnt.reverse()
k_str = to_bin(K)
while len(k_str) < 40:
    k_str = '0' + k_str

for j in range(len(cnt)):
    if k_str[j] == '1':
        tmp_ans = 0
        for k in range(len(cnt)):
            power = 39 - k
            if k <= j - 1:
                if k_str[k] == '0':
                    tmp_ans += cnt[k] * (2 ** power)
                else:
                    tmp_ans += (N - cnt[k]) * (2 ** power)
            elif k == j:
                tmp_ans += cnt[k] * (2 ** power)
            else:
                tmp_ans += max(cnt[k], N - cnt[k]) * (2 ** power)
        ans = max(ans, tmp_ans)
tmp_ans = 0
for k in range(len(cnt)):
    power = 39 - k
    if k_str[k] == '0':
        tmp_ans += cnt[k] * (2 ** power)
    else:
        tmp_ans += (N - cnt[k]) * (2 ** power)
ans = max(ans, tmp_ans)
print(ans)

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

max_dig = 40


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

for i in range(max_dig):
    cnt = 0
    for j in range(n):
        if (a[j] >> (max_dig-i-1)) & 1:
            cnt += 1

    cost0 = 2**(max_dig-i-1) * cnt
    cost1 = 2**(max_dig-i-1) * (n - cnt)
    
    if dp[i][1] != -1:
        dp[i+1][1] = dp[i][1] + max(cost0, cost1)
    
    if dp[i][0] != -1:
        if (k >> (max_dig-i-1)) & 1:
            dp[i+1][1] = max(dp[i+1][1], dp[i][0] + cost0)
    
    if dp[i][0] != -1:
        if (k >> (max_dig-i-1)) & 1:
            dp[i+1][0] = dp[i][0] + cost1
        else:
            dp[i+1][0] = dp[i][0] + cost0

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

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

b=0
while k > 0:
  k = k>>1
  b +=1

c=[0]*b
for i in range(b):
   m=2**i
   for j in range(n):
      c[i]+= 1 if a[j]&m else 0

x = 0
for i in range(b-1,-1,-1):
  if 2*c[i]<n:
    if x+2**i <= u:
      x += 2**i

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

print(t)

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

    MAX_DIGIT = 50

    
    
    
    dp = [[-1] * 2 for _ in range(MAX_DIGIT+5)]
    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][1] != -1:
            dp[d+1][1] = max(dp[d+1][1], dp[d][1] + max(cost0, cost1))

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

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

main()

Solution (Python):
n, k = map(int, input().split())
ls = list(map(int, input().split()))
ls2 = list(map(lambda x: bin(x)[2:], ls))
m = max(map(len, ls2))
m = max(m, len(bin(k)[2:]))
ls2 = [s.rjust(m, '0') for s in ls2]
res = []
for i in range(m):
    if 2**(m - i - 1) > k:
        continue
    count = 0
    for s in ls2:
        if i < len(s) and s[i] == '0':
            count += 1
    if count < (n + 1) // 2:
        res.append('0')
    else:
        res.append('1')

x = 0
mm = len(res)
for i, c in enumerate(res):
    if c == '1':
        c = 2**(mm - i - 1)
        if x + c <= k:
            x += c

y = 0
for a in ls:
    y += x ^ a
print(y)

Solution (Python):
n, k = map(int, input().split())
ls = list(map(int, input().split()))
ls2 = list(map(lambda x: bin(x)[2:], ls))
m = max(map(len, ls2))
m = max(m, len(bin(k)[2:]))
ls2 = [s[::-1] for s in ls2]
res = []
for i in range(m):
    c0 = 0
    c1 = 0
    for s in ls2:
        if i < len(s):
            if s[i] == '0':
                c0 += 1
            else:
                c1 += 1
        else:
            c0 += 1
    if c1 > c0:
        res.append('0')
    else:
        res.append('1')
    x = int(''.join(res[::-1]), 2)
    if x > k:
        break

x = 0
mm = len(res)
for i, c in enumerate(res[::-1]):
    if c == '1':
        c = 2**(mm - i - 1)
        if x + c <= k:
            x += c

y = 0
for a in ls:
    y += x ^ a
print(y)

Solution (Python):
N, K = map(int, input().split())
A = [int(x) for x in input().split()]
B = [0] * 40
for a in A:
  _a = a
  for i in range(40):
    B[i] += _a % 2
    _a >>= 1
KB = [0] * 40
_K = K
P = [[0, 0] for _ in range(40)]
for i in range(40):
  KB[i] = _K % 2
  _K >>= 1
  P[i] = [B[i] * 2 ** i, (N - B[i]) * 2 ** i]
cnt = 0
free = 0
for i in range(39, -1, -1):
  if free == 1:
    cnt += max(P[i])
  elif KB[i] == 0:
    cnt += P[i][0]
  elif P[i][0] >= P[i][1]:
    cnt += P[i][0]
    free = 1
  else:
    cnt += P[i][1]
print(cnt)

Solution (Python):
N, K = map(int, input().split())
A = [int(x) for x in input().split()]
B = [0] * 40
for a in A:
  _a = a
  for i in range(40):
    B[i] += _a % 2
    _a >>= 1
KB = [0] * 40
_K = K
P = [[0, 0] for _ in range(40)]
for i in range(40):
  KB[i] = _K % 2
  _K >>= 1
  P[i] = [B[i] * 2 ** i, (N - B[i]) * 2 ** i]
cnt = 0
free = 0
for i in range(39, -1, -1):
  if free == 1:
    cnt += max(P[i])
  elif KB[i] == 0:
    cnt += P[i][0]
  elif P[i][0] >= P[i][1]:
    cnt += P[i][0]
    free = 1
  else:
    cnt += P[i][1]
print(cnt)

Solution (Python):
n,k = (int(x) for x in input().split())
a = list(map(int, input().split()))
max_digit = 50
dp = [[-1,-1] for _ in range(max_digit + 10)]
dp[0][0] = 0

for i in range(max_digit):
  mask = 1<<(max_digit - i - 1)
  num = 0
  for j in range(n):
    if(mask&a[j]):
      num += 1
  cost0 = num*mask
  cost1 = (n-num)*mask
  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(mask&k):
      dp[i+1][1] = max(dp[i+1][1], dp[i][0] + cost0)
      dp[i+1][0] = max(dp[i+1][0], dp[i][0] + cost1)
    else: 
      dp[i+1][0] = max(dp[i+1][0], dp[i][0] + cost0)

print(max(dp[max_digit]))

Solution (Python):

N,K = map(int,input().split())
A = list(map(int,input().split()))
Abin = []
Kbin = []
count = 0

for a in A:
    b = bin(a)
    b = b.lstrip("0b")
    blen = len(b)
    for j in range(40-blen):
        b = "0"+b
    Abin.append(b)
    
for i in range(40):
    t = 40-i-1
    if (2**t)+count > K:
        Kbin.append(0)
    else:
        count0 = 0
        count1 = 0
        for j in range(N):
            nbit = Abin[j][i]
            if nbit == "0":
                count0+=1
            else:
                count1+=1
        
        if count0 >= count1:
            Kbin.append(1)
            count+=(2**t)
        else:
            Kbin.append(0)
            

Bin = 0
for i in range(40):
    t = 40-i-1
    Bin+=(Kbin[i]*(2**t))
ans = 0
for a in A:
    ans+=(Bin^a)
print(ans)

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

mbl = len(format(max(A + [K]), 'b'))
cnt = [0] * mbl

for i in range(mbl):
    for a in A:
        if a & (1 << i):
            cnt[i] += 1

x = 0
for i in range(mbl - 1, -1, -1):
    if N // 2 >= cnt[i] and K >= x + (1 << i):
        x += (1 << i)

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

print(ans)

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

b = len(format(10**12,'b'))

a = [format(x,'0{}b'.format(b)) for x in a]

k = format(k,'0{}b'.format(b))


ans = ''
flag = False
for i in range(b):
    one = 0
    zero = 0
    for j in range(n):
        if a[j][i]=='1':
            one += 1
        else:
            zero += 1
    if one < zero:
        if flag:
            ans += '1'
            continue
        else:
            if k[i]=='1':
                ans += '1'
            else:
                ans += '0'
    else:
        ans += '0'
        if k[i]=='1':
            flag = True

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

print(ans2)

Solution (Python):
n,k = map(int,input().split())
a = list(map(int,input().split()))
m = max(k,max(a))
b = 1
count = 0
while m > b:
    b *= 2
    count += 1
p = 2**(count-1)
k2 = 0
ans = 0
for i in range(count):
    count1 = 0
    for j in range(n):
        if a[j] // p == 1:
            a[j] -= p
            count1 += 1
    if count1 >= n - count1:
        ans += count1*p
    else:
        if k2 + p <= k:
            ans += (n-count1)*p
            k2 += p
        else:
            ans += count1*p
    p = p//2
print(ans)

Solution (Python):

n,k = map(int,input().split())
a = list(map(int,input().split()))
now = 2 ** len(bin(k)[2:])
can = 0
while now:
  tmp = 0
  for i in range(n):
    if a[i] ^ now > a[i]:
      tmp += 1
  if tmp * 2 > n:
    can += now
    if can > k:
      can -= now
  now //= 2
ans = 0
for i in range(n):
  ans += a[i] ^ can

print(ans)

Solution (Python):

n,k = map(int,input().split())
a = list(map(int,input().split()))
now = 2 ** len(bin(k)[2:])
can = 0
while now:
  tmp = 0
  for i in range(n):
    if a[i] ^ now > a[i]:
      tmp += 1
  if tmp * 2 > n:
    can += now
    if can > k:
      can -= now
  now //= 2
ans = 0
for i in range(n):
  ans += a[i] ^ can

print(ans)

Solution (Python):
from math import log2

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

Bits = [0 for _ in range(41)]
for i, a in enumerate(A):
    b = bin(a)[2:]
    for i in range(len(b)-1, -1, -1):
        Bits[len(b)-i-1] += int(b[i])

P = 0
for i in range(40, -1, -1):
    b = Bits[i]
    if b <= N-b and P + 2**i <= K:
        P += 2**i

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

Solution (Python):
N, K = map(int, input().split())
a = [int(i) for i in input().split()]
m = -1
for i in a:
  if i>m:
    m = i
m = max(K,m)
s = bin(m)[2:]
length = len(s)
ls = [[0,length-i-1] for i in range(length)]

for i in a:
  s = bin(i)[2:]
  while len(s)<length:
    s = '0'+s
  for j in range(length):
    if s[j]=='1':
      ls[j][0] += 1
dic = {}
for i in range(length):
  x, n = ls[i]
  s = (2**n)*(N-x)-(2**n)*x
  dic[n]=s
s = bin(K+1)[2:]
ils = [len(s)-i-1 for i in range(len(s)) if s[i]=='1']
xls = []
for i in range(len(ils)):
  m = ''
  for j in range(ils[i]):
    if dic[j]>0:
      m+='1'
    else:
      m+='0'
  m += '0'
  while len(m)<len(s):
    m += s[len(s)-len(m)-1]
  m = m[::-1]
  xls += [int(m,2)]

ans = 0
for x in xls:
  h = 0
  for u in a:
    h += x^u
  if h>ans:
    ans = h
print(ans)

Solution (Python):


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

lenbin = len(bin(max(max(a), k))) - 2
bitcnt = [0] * lenbin

for i in range(lenbin):
    for ai in a:
        if ai & (1 << i):
            bitcnt[i] += 1

x = 0
for i in range(lenbin - 1, -1, -1):
    if bitcnt[i] <= n // 2 and x + (1 << i) <= k:
        x += (1 << i)

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

print(ans)

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))



N,K = II()
A = III()

k = format(K,'b')
k = k.zfill(50)

B = ['0']*N
for i in range(N):
    B[i] = str(format(A[i],'b')).zfill(50)

val = str()
flag = False
for i in range(50):
    count0 = 0
    count1 = 0
    for j in range(N):
        if B[j][i]=='0':
            count0 += 1
        else:
            count1 += 1
    if k[i]=='1':
        if count0 > count1:
            val += '1'
        else:
            val += '0'
            flag = True
    else:
        if count0 >= count1:
            if flag:
                val += '1'
            else:
                val += '0'
        else:
            val += '0'

val = int(val,2)
ans = 0
for i in range(N):
    ans += val^A[i]

print(ans)

Solution (Python):

import math



N,K = list(map(int,input().split(" ")))
As = list(map(int,input().split(" ")))
dp =[ [ -1 for  _ in range(2)] for _ in range (51)]
dp[0][0] = 0 
for d in range(50):
    mask =  1 << (50 - d - 1) 
    cot = 0
    for A in As:
        if (A & mask): 
            cot += 1
    cost0 = mask * cot 
    cost1 = mask * (N -cot) 
    
    if dp[d][1] != -1: 
        dp[d + 1][1] = max( dp[d][1] + cost0,dp[d][1] + cost1    )
    if dp[d][0] !=-1: 

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

        else:
            dp[d + 1][0] = max(dp[d][0]  , dp[d][0] + cost0)

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