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):
import math
N, K = map(int, input().split())
A = list(map(int, input().split()))
log2K = int(math.log2(10**12))+1
count_bit = [0 for i in range(log2K)]
for ai in A:
    for i in range(log2K):
        if ai & 1:
            count_bit[i] += 1
        ai = ai >> 1
b = 2**(log2K)
ans = 0
k_sum = 0
for i in range(log2K-1, -1, -1):
    if K >> i & 1:
        tmp = k_sum
        b = 1
        for j in range(i):
            tmp += max(count_bit[j], N-count_bit[j]) * b
            b *= 2
        tmp += count_bit[i] * b
        ans = max(tmp, ans)
        k_sum += (N-count_bit[i]) * b
    else:
        k_sum += count_bit[i] * (2**i)
ans = max(k_sum, ans)
print(ans)

Solution (Python):
def main():
    import sys
    sys.setrecursionlimit(311111)
    
    ikimasu = sys.stdin.buffer.readline
    ini = lambda: int(ins())
    ina = lambda: list(map(int, ikimasu().split()))
    ins = lambda: ikimasu().strip()
    n,k = ina()
    tmp = ina()
    x = 1<<55
    rick = 0
    used = 0
    for _ in range(55+1):
        tmp1 = 0
        for i in tmp:
            if(i&x):
                tmp1+=1
        if(tmp1>=(n-tmp1)):
            rick+=x*tmp1
        else:
            if((x+used<=k)):
                rick+=x*(n-tmp1)
                used +=x
            else:
                rick+=x*tmp1
        x>>=1
    print(rick)


    


        
        
        


    
        


        


    




















if __name__ == "__main__":
    main()

Solution (Python):
def main():
    import sys
    sys.setrecursionlimit(311111)
    
    ikimasu = sys.stdin.buffer.readline
    ini = lambda: int(ins())
    ina = lambda: list(map(int, ikimasu().split()))
    ins = lambda: ikimasu().strip()
    n,k = ina()
    tmp = ina()
    x = 1<<55
    rick = 0
    used = 0
    for _ in range(55+1):
        tmp1 = 0
        for i in tmp:
            if(i&x):
                tmp1+=1
        if(tmp1>=(n-tmp1)):
            rick+=x*tmp1
        else:
            if((x+used<=k)):
                rick+=x*(n-tmp1)
                used +=x
            else:
                rick+=x*tmp1
        x>>=1
    print(rick)


    


        
        
        


    
        


        


    




















if __name__ == "__main__":
    main()

Solution (Python):
n, k = map(int, input().split())
A = sorted(map(int, input().split()), reverse=True)

cnt = [0 for _ in range(100)]
max_a = A[0]
k += 1
index_k = 0
index_a = 0

for i in range(100):
    tmp = 2 ** i

    if tmp > max_a:
        index_a = i - 1
        break

    for a in A:
        if a < tmp:
            break
        if (a >> i) & 1:
            cnt[i] += 1

for i in range(100):
    tmp = 2 ** i

    if tmp > k:
        index_k = i - 1
        break

best = [0, ]

for i, c in enumerate(cnt[: index_k + 1]):

    best.append(best[-1] + max(c, n - c) * 2 ** i)

initial = 0

if index_a > index_k:

    initial = sum(map(lambda x: 2 ** x[0] * x[1],
                      enumerate(cnt[index_k + 1 : index_a + 1], index_k + 1)))
                    

equal = [initial, ]

for i, c in enumerate(cnt[index_k::-1]):

    if k >> (index_k - i) & 1:
        equal.append(equal[-1] + (n - c) * 2 ** (index_k - i))
    else:
        equal.append(equal[-1] + c * 2 ** (index_k - i))

ans = 0

for i in range(index_k + 1):

    if (k >> i) & 1:
        ans = max(ans, best[i] + cnt[i] * 2 ** i + equal[-(i + 2)])

print(ans)

Solution (Python):
n, k = map(int, input().split())
A = sorted(map(int, input().split()), reverse=True)
cnt = [0 for _ in range(100)]
m = A[0]

for i in range(100):
    ten = 2 ** i
    if ten > m:
        break
    for a in A:
        if a < ten:
            break
        if (a >> i) & 1:
            cnt[i] += 1

for m in range(100):
    if 2 ** m > k+1:
        j = m-1
        break

initial = 0
if i > j:
    for m, c in enumerate(cnt[j + 1: i + 1], j + 1):
        initial += 2 ** m * c

best = [0, ]
for m, c in enumerate(cnt[: j + 1]):
    best.append(best[-1] + max(c, n - c) * 2 ** m)

K = list()
equal = [initial, ]
for m, c in enumerate(cnt[j::-1]):
    y = (k+1 >> (j-m)) & 1
    K.append(y)
    if y==1:
        equal.append(equal[-1] + (n - c) * 2 ** (j-m))
    else:
        equal.append(equal[-1] + c * 2 ** (j-m))

ans = 0
K.reverse()

for i in range(j+1):
    if K[i]:
        ans = max(ans, best[i] + 2 ** i * cnt[i] + equal[-(i + 2)])

print(ans)

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

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

Solution (Python):









def solve(N, K, A):
    import math
    max_K = 0
    for i in reversed(list(range(int(math.log2(K + 1)) + 1))):
        cnt = 0
        for a in A:
            if a >> i & 1:
                cnt += 1
        if cnt <= N // 2:
            if max_K + (1 << i) <= K:
                max_K += 1 << i
    ans = 0
    for a in A:
        ans += a ^ max_K
    print(ans)



if __name__ == '__main__':
    N, K = map(int, input().split())
    A = [int(i) for i in input().split()]
    solve(N, K, A)

Solution (Python):
import math
N, K = map(int, input().split())
A = list(map(int, input().split()))
log2K = int(math.log2(10**12))+1
count_bit = [0 for i in range(log2K)]
for ai in A:
    for i in range(log2K):
        if ai & 1:
            count_bit[i] += 1
        ai = ai >> 1
b = 2**(log2K)
X = 0
for c in count_bit[::-1]:
    b //= 2
    if c*2 < N and X + b <= K:
        X += b
ans = 0
for ai in A:
    ans += X ^ ai
print(ans)

Solution (Python):
import sys

icase=0
if icase==0:
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
elif icase==1:
    n,k=4,9
    a=[7,4,0,3]
elif icase==2:
    n,k=3,7
    a=[1,6,3]
elif icase==3:
    n,k=1,0
    a=[1000000000000]

if k==0:
    print(sum(a))
    sys.exit()
    
kk=[0]*42
kkk=k
kcnt=0
while kkk>0:
    kk[kcnt]=kkk%2
    kcnt+=1
    kkk=kkk//2
    
f=[0]*42
for ai in a:
    icnt=0
    while ai>0:
        f[icnt]+=ai%2
        ai=ai//2
        icnt+=1

n2=n//2+1
fm=[0]*42

flg1=0
flg2=0
for i in range(41,-1,-1):
    if flg1==0 and kk[i]==0:
        fm[i]=0
    if flg1==0 and kk[i]==1:
        flg1=1
    if flg1==0:
        fm[i]=f[i]        
        continue

    if kk[i]==1 and f[i]>=n2 and flg2==0:
        flg2=1
    if kk[i]==1 or (kk[i]==0 and flg2==1):
        if f[i]<n2:
            fm[i]=n-f[i]
        else:
            fm[i]=f[i]        
    else:
        fm[i]=f[i]        
    
smax=0
idx=1
for i in range(len(fm)):
    smax+=idx*fm[i]
    idx*=2

print(smax)

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

B = 0
K_copy = K
while K_copy > 0:
  B += 1
  K_copy //= 2

C = [0 for d in range(40)] 
for d in range(40):
  for i in range(N):
    if A[i] % 2 == 1:
      C[d] += 1
    A[i] //= 2

ans = 0
for d in range(B, 40):
  ans += 2**d * C[d]
  
bit_K = [0 for _ in range(B)]
for d in range(B):
  if K % 2 == 1:
    bit_K[d] = 1
  K //= 2

if B == 0:
  print(ans)
  sys.exit()
    

DP = [[0 for fill in range(2)] for d in range(B)]

DP[B-1][0] = C[d]
DP[B-1][1] = N - C[d]

for d in range(B-2,-1,-1):
  DP[d][0] = DP[d+1][0] * 2 + max(C[d], N - C[d])
  if bit_K[d] == 1:
    DP[d][0] = max(DP[d][0], DP[d+1][1] * 2 + C[d])
  DP[d][1] = DP[d+1][1] * 2 + C[d] + (N - 2 * C[d])*(bit_K[d])
  
  
ans += max(DP[0])
print(ans)

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

digit_n = 0
kk = k
while kk > 0:
    kk >>= 1
    digit_n += 1

count = [0] * digit_n
mask = ~((1 << digit_n) - 1)

ans = 0
for i in range(n):
    ans += a[i] & mask
    for j in range(digit_n):
        if (a[i] >> j) & 1:
            count[j] += 1 

dp = [[0] * (digit_n + 1) for _ in range(2)]

for i in range(1, digit_n + 1):
    j = digit_n - i
    bit = (k >> j) & 1
    dp[0][i] = (dp[0][i-1] << 1) + (n - count[j] if bit else count[j])
    if dp[1][i-1]:
        dp[1][i] = (dp[1][i-1] << 1) + max(n - count[j], count[j])
    if bit == 1:
        dp[1][i] = max(dp[1][i], (dp[0][i-1] << 1) + count[j])
ans += max(dp[0][-1], dp[1][-1])
print(ans)

Solution (Python):
n, k = map(int, input().split())
A = list(map(int, input().split()))
M = 40
C = [[0]*2 for _ in range(M+1)]
for a in A:
  for i in range(M+1):
    C[i][a>>i & 1] += 1
dp = [[0]*2 for _ in range(M+1)]
dp[M][1] = -float("inf")
for i in range(M-1, -1, -1):
  j = k>>i & 1
  dp[i][0] = dp[i+1][0]*2 + C[i][j^1]
  dp[i][1] = dp[i+1][1]*2 + max(C[i])
  if j:
    dp[i][1] = max(dp[i][1], dp[i+1][0]*2 + C[i][1])
ans = max(dp[0])
print(ans)

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

    l = []
    for _ in range(40):
        cnt = 0
        for i in range(n):
            if a[i] & 1:
                cnt += 1
            a[i] >>= 1
        l.append(cnt)

    pows = [1]
    for _ in range(39):
        pows.append(pows[-1] * 2)

    if k == 0:
        print(sum([l[i] * pows[i] for i in range(40)]))
        exit()

    
    ans1 = 0
    for i in range(k.bit_length() - 1):
        if l[i] < n - l[i]:
            ans1 += (n - l[i]) * pows[i]
        else:
            ans1 += l[i] * pows[i]
    for i in range(k.bit_length() - 1, 40):
        ans1 += l[i] * pows[i]

    
    ans2 = 0
    ans3 = 0
    for i in range(40):
        if l[i] < n - l[i]:
            if k & 1:
                ans2 += (n - l[i]) * pows[i]
            else:
                ans2 += l[i] * pows[i]
            ans3 += (n - l[i]) * pows[i]
        else:
            if k & 1:
                ans2 = ans3 + l[i] * pows[i]
            else:
                ans2 += l[i] * pows[i]
            ans3 += l[i] * pows[i]
        k >>= 1

    print(max(ans1, ans2))

main()

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

dp = [n]*41

for i in range(n):
    i_bit = bin(al[i])[2:]
    lenb = len(i_bit)
    for j in range(lenb-1,-1,-1):
        dp[lenb-1-j] -= int(i_bit[j])

temp = k
res = 0
m = n//2

for i in range(40,-1,-1):
    if dp[i] > m and 2**i <= temp:
        temp -= 2**i
        res += (2**i)*(dp[i]) 
    else:
        res += (2**i)*(n-dp[i])

print(res)

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

lst=[0]*50


for i in a:
  for j in range(50):
    if (i>>j)%2==1:
      lst[j]+=1

k=bin(k)[2:]

dp=[[0]*2 for i in range(len(k)+1)]


for i in range(len(k)):
  if k[i]=='1':
    dp[i+1][0]=dp[i][0]+(n-lst[len(k)-i-1]*2)*(2**(len(k)-i-1))
    dp[i+1][1]=dp[i][0]
  else:
    dp[i+1][0]=dp[i][0]

  if i==0:
      continue
  
  dp[i+1][1]=max(dp[i+1][1],dp[i][1],dp[i][1]+(n-lst[len(k)-i-1]*2)*(2**(len(k)-i-1)))


print(sum(a)+max(dp[-1][0],dp[-1][1]))

Solution (Python):
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    l = len(bin(max(max(A), K))) - 2
    L = [0] * l
    ans = 0
    k = 0
    for a in A:
        for j in range(l):
            if (a >> j) & 1 == 1:
                L[j] += 1
    for i, b in enumerate(L[::-1]):
        if b < N - b:
            if K >= k + 2 ** (l - i - 1):
                b = N - b
                k += 2**(l - i - 1)
        ans += b * (2**(l - i - 1))
    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())
A = list(map(int,readline().split()))

dp = [[0]*2 for i in range(41)]

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

Solution (Python):

import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys


readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, A):
    c = Counter()
    for a in A:
        for i in range(64):
            if a & (1 << i) != 0:
                c[i] += 1

    x = 0
    for i in range(63, -1, -1):
        m = 1 << i
        if x + m > K:
            continue
        if c[i] <= N // 2:
            x += m

    return sum(map(lambda a: x ^ a, A))


def main():
    N, K = read_int_n()
    A = read_int_n()

    print(slv(N, K, A))


if __name__ == '__main__':
    main()

Solution (Python):
N,K = map(int,input().split())
A = list(map(int,input().split()))
t = 2**40
ans = 0

while t:
  c = sum([(A[n]&t)//t for n in range(N)])
  if K<t or c*2>=N:
    ans+=t*c
  else:
    ans+=t*(N-c)
    K-=t
  t//=2

print(ans)

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

d=[0 for i in range(40)]
for i in a:
  for j in range(40):
    d[j]+=1 if i&(2**j) else 0
s=[]
ss=0
for i in range(40):
  ss+=(2**i)*max(d[i],n-d[i])
  s.append(ss)
s.append(0)
mx=0
isum=0
for i in range(39,-1,-1):
  if k&(2**i):
    mx=max(mx,isum+(2**i)*d[i]+s[i-1])
    isum+=(2**i)*(n-d[i])
  else:
    isum+=(2**i)*d[i]
mx=max(mx,isum)
print(mx)

Solution (Python):
n, k = map(int, input().split())
A = tuple(map(int, input().split()))
ones = [0] * k.bit_length()
for a in A:
    for i in range(k.bit_length()):
        ones[i] += (a >> i) & 1

x = 0
for idx, one in enumerate(ones[::-1]):
    if n - one > one:
        xx = 2**(len(ones)-1-idx)
        if x + xx > k:
            continue
        else:
            x += xx
ans = 0
for a in A:
    ans += a ^ x
print(ans)

Solution (Python):
def cin():  return list(map(int,input().split()))

N, K = cin()
A = cin()

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

for i in range(1, MAX_DIGIT):
    mask = (1 << (MAX_DIGIT - i - 1))
    cnt = 0
    for j in range(N):  cnt += bool(A[j] & mask)
    cost0 = mask * cnt
    cost1 = mask * (N - cnt)
    if(dp[i - 1][1] != -1):  dp[i][1] = max(dp[i][1], dp[i - 1][1] + max(cost0, cost1))
    if(dp[i - 1][0] != -1):
        if(K & mask):  dp[i][1] = max(dp[i][1], dp[i - 1][0] + cost0)
        if(K & mask):  dp[i][0] = max(dp[i][0], dp[i - 1][0] + cost1)
        else:  dp[i][0] = max(dp[i][0], dp[i - 1][0] + cost0)
        
ans = max(dp[MAX_DIGIT - 1][0], dp[MAX_DIGIT - 1][1])
print(ans)

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

d = [0] * 40
for i in range(n):
  for j in range(40):
    if a[i] & (1<<j):
      d[j] += 1
s = 0
for i in range(39,-1,-1):
  if s + 2**i > k:
    continue
  if d[i] > n//2:
    continue
  s += 2**i

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

Solution (Python):
import numpy as np
N,K = map(int,input().split())
A = list(map(int,input().split()))
MAXBITS = 40
bits = np.ndarray((N, MAXBITS), dtype=int)
for i in range(N):
    a = A[i]
    bits[i] = np.array([(a >> j) & 1 for j in range(MAXBITS-1, -1, -1)])
sm = bits[0]
for b in bits[1:]:
    sm += b
lower = False
Kbits = np.array([(K >> j) & 1 for j in range(MAXBITS-1, -1, -1)])
ans = 0
for i in range(MAXBITS):
    ones = sm[i]
    zeros = N-sm[i]
    base = 2**(MAXBITS-i-1)
    bit = 0
    if ones >= zeros:
        bit = 0
    elif lower or Kbits[i] == 1:
        bit = 1
    if Kbits[i] > bit:
        lower = True
    ans += ones*base if bit == 0 else zeros*base
print(ans)

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

dp = [[-1 for _ in range(2)]for _ in range(51)]
dp[0][0] = 0
MAX_DIGIT = 50

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

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






for d in range(60, -2, -1):
    

    
    
    
    

    
    
    
    
    

    if d != -1 and (K & 1 << d) == 0:
        continue

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

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

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

print(res)

Solution (Python):
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("YES") if fl else print("NO")
import collections
import math
import itertools
import heapq as hq
n,k  = ma()
A  = lma()
mx = max(A)
lm = len(bin(max(mx,k)))-2
ls = [0]*lm
for a in A:
    ba = bin(a)[::-1]
    for i in range(len(ba)-2):
        if ba[i]=="1":
            ls[i]+=1

bk = bin(k)[2:].zfill(lm)
bk=bk[::-1]
lk = len(bk)
def score(idx,f2=False):
    f=False
    ret=0
    if bk[idx]=="1":
        f=True
    for i in range(lm):
        if f2:
            if bk[i]=="0":
                ret+=ls[i]*2**i
            else:
                ret+=max(ls[i],n-ls[i])*2**i
            continue
        if f:
            if i<idx:
                ret+=max(ls[i],n-ls[i])*2**i
            elif i==idx:
                ret +=ls[i]*2**i
            else:
                if bk[i]=="0":
                    ret+=ls[i]*2**i
                else:
                    ret+=max(ls[i],n-ls[i])*2**i
        else:
            if bk[i]=="0":
                ret+=ls[i]*2**i
            else:
                ret+=max(ls[i],n-ls[i])*2**i

    return ret
ans = 0
for i in range(1,lk):
    tmp = score(i)
    
    ans = max(ans,tmp)
ans = max(ans,score(0,f2=True))
print(ans)

Solution (Python):
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  


N,K = MI()
K += 1
k = K.bit_length()
K_bit = [(K >> i) & 1 for i in range(k)]  
A = LI()
A_bit = [[(A[i] >> j) & 1 for j in range(k)] for i in range(N)]  

X = [0]*(k+1)  
for i in range(k):
    a = sum(A_bit[j][i] == 0 for j in range(N))  
    X[i+1] = X[i]
    if a >= N//2+1:
        X[i+1] += 2**i


def f(x):
    return sum(x^A[i] for i in range(N))


ans = 0
for i in range(k-1,-1,-1):
    if K_bit[i] == 1:
        ans = max(ans,f(((K >> (i+1)) << (i+1))+X[i]))

print(ans)

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

L = 40
bc = [0] * L
for i in range(L):
    for a in A:
        if a&(1<<i):
            bc[i] += 1

dp = [[-1,-1] for _ in range(L+1)]
dp[L][0] = 0
for i in range(L-1,-1,-1):
    c = (K>>i)&1
    for l in range(2):
        if dp[i+1][l] < 0: continue
        for d in range(2):
            if l==0 and d > c: continue
            nl = 0 if l==0 and d==c else 1
            dp[i][nl] = max(dp[i][nl], dp[i+1][l] + 2**i * (N-bc[i] if d else bc[i]))

print(max(dp[0]))

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

bit_cnt = [0] * 40

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

x = 0
for i in range(39, -1, -1):
    if x + (1 << i) <= k and bit_cnt[i] <= n - bit_cnt[i]:
        x += (1 << i)

print(sum([x ^ y for y in arr]))

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
MAX = max(len(bin(K))-2, len(bin(max(A)))-2)
bK = bin(K)[2:].zfill(MAX)
degs = [0]*MAX 
for i in range(N):
    b = bin(A[i])[2:].zfill(MAX)
    for d in range(MAX):
        if b[d] == "1":
            degs[d] += 1

tot = 0
dp = [0]*MAX 
for f in range(MAX):
    t = 2 ** (MAX-1)
    ans = 0
    is_free = 0
    for i in range(MAX):
        d = degs[i]
        if i == f:
            if bK[i] == "1":
                is_free = 1
        elif i < f:
            if bK[i] == "1":
                d = max(d, N-d)
        elif i > f and is_free:
            d = max(d, N-d)
        ans += t * d
        t //= 2
    tot = max(tot, ans)
t = 2 ** (MAX-1)
ans = 0
for i in range(MAX):
    d = degs[i]
    if bK[i] == "1":
        d = max(d, N-d)
    ans += t*d
    t //= 2
tot = max(tot, ans)    
print(tot)

Solution (Python):
INFTY = 10**12
N,K = map(int,input().split())
A = list(map(int,input().split()))
A = [bin(A[i])[2:] for i in range(N)]
for i in range(N):
    A[i] = (40-len(A[i]))*"0"+A[i]
K = bin(K)[2:]
m = len(K)
K = (40-len(K))*"0"+K
dp = [[-INFTY for _ in range(2)] for _ in range(41)]
dp[0][0] = 0
for i in range(1,41):
    for small in range(2):
        for d in range(2):
            ni = i
            nsmall = small
            nd = int(K[i-1])
            cnt = 0
            for j in range(N):
                cnt += int(A[j][i-1])^d
            if small==0:
                if d>nd:continue
                if d<nd:nsmall=1
            dp[ni][nsmall] = max(dp[ni][nsmall],2*dp[i-1][small]+cnt)
tot = max(dp[40][0],dp[40][1])
print(tot)

Solution (Python):
INFTY = 10**12
N,K = map(int,input().split())
A = list(map(int,input().split()))
A = [bin(A[i])[2:] for i in range(N)]
for i in range(N):
    A[i] = (40-len(A[i]))*"0"+A[i]
K = bin(K)[2:]
m = len(K)
K = (40-len(K))*"0"+K
dp = [[-INFTY for _ in range(2)] for _ in range(41)]
dp[0][0] = 0
for i in range(1,41):
    nd = int(K[i-1])
    cnt0 = 0
    cnt1 = 0
    for j in range(N):
        cnt0 += int(A[j][i-1])
        cnt1 += 1-int(A[j][i-1])
    if nd==0:
        dp[i][0] = 2*dp[i-1][0]+cnt0
    else:
        dp[i][0] = 2*dp[i-1][0]+cnt1
    f1 = 2*dp[i-1][1]+max(cnt0,cnt1)
    if nd==0:
        f0 = -INFTY
    else:
        f0 = 2*dp[i-1][0]+cnt0
    dp[i][1] = max(f1,f0)
tot = max(dp[40][0],dp[40][1])
print(tot)

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

bit_cnts = [0]*41
for a in al:
    for i in range(41):
        if a&(1<<i) > 0:
            bit_cnts[i] += 1


dp_same = [0]*42
dp_small = [0]*42
small_flag = False
for i in range(41,0,-1):
    curr_bit = i-1
    kbit = 0
    if k&(1<<curr_bit) > 0: kbit = 1
    if kbit == 0:
        dp_same[i-1] = dp_same[i] + pow(2,curr_bit)*bit_cnts[curr_bit]
        if small_flag:
            dp_small[i-1] = dp_small[i] + pow(2,curr_bit)*(n-bit_cnts[curr_bit])
            dp_small[i-1] = max(dp_small[i-1], dp_small[i] + pow(2,curr_bit)*(bit_cnts[curr_bit]))
    else:
        dp_same[i-1] = dp_same[i] + pow(2,curr_bit)*(n-bit_cnts[curr_bit])
        dp_small[i-1] = dp_same[i]+pow(2,curr_bit)*(bit_cnts[curr_bit])
        if small_flag:
            dp_small[i-1] = max(dp_small[i-1], dp_small[i] + pow(2,curr_bit)*(n-bit_cnts[curr_bit]))
            dp_small[i-1] = max(dp_small[i-1], dp_small[i] + pow(2,curr_bit)*(bit_cnts[curr_bit]))
        small_flag = True

ans = max(dp_same[0],dp_small[0])
print(ans)

Solution (Python):
N,K = map(int,input().split())
A = list(map(int,input().split()))
UP = max(A)
UL = UP.bit_length()
KL = K.bit_length()
MAX = max(UL,KL)
INF = float("inf")

dp = [[-INF] * 2 for _ in range(MAX+1)] 
dp[0][0]=0
ZF = True
L = [[0]*2 for _ in range(MAX)]
for i in range(N):
  for j in range(MAX):
    if A[i]>>j&1 == 1:
      L[MAX-1-j][1] += 1
    else:
      L[MAX-1-j][0] += 1



for i in range(MAX):
  fac = pow(2,(MAX-1-i))
  if K>>(MAX-1-i)&1 == 1:
    ZF = False
  if ZF: 
    dp[i+1][0] = dp[i][0] + fac*L[i][1]
    dp[i+1][1] = 0
  else:
    if K>>(MAX-1-i)&1 == 1:
      kbit = 1
    else:
      kbit = 0
    
    if kbit == 1: 
      dp[i+1][1] = max(dp[i][1] + fac*max(L[i]), dp[i][0] + fac*L[i][1]) 
      dp[i+1][0] = dp[i][0] + fac*L[i][0] 
    else: 
      dp[i+1][1] = dp[i][1] + fac*max(L[i]) 
      dp[i+1][0] = dp[i][0] + fac*L[i][1] 

ans = max(dp[MAX])
print(ans)

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

bit_cnts = [0]*41
for a in al:
    for i in range(41):
        if a&(1<<i) > 0:
            bit_cnts[i] += 1


dp_same = [-1]*42
dp_small = [-1]*42
dp_small[41] = -1
dp_same[41] = -1
for i in range(41,0,-1):
    curr_bit = i-1
    kbit = 0
    if k&(1<<curr_bit) > 0: kbit = 1
    if kbit == 0:
        dp_same[i-1] = dp_same[i] + pow(2,curr_bit)*bit_cnts[curr_bit]
        
        if dp_small[i] > -1:
            dp_small[i-1] = dp_small[i] + pow(2,curr_bit)*(n-bit_cnts[curr_bit])
            dp_small[i-1] = max(dp_small[i-1], dp_small[i] + pow(2,curr_bit)*(bit_cnts[curr_bit]))
    else:
        dp_same[i-1] = dp_same[i] + pow(2,curr_bit)*(n-bit_cnts[curr_bit])
        dp_small[i-1] = max(0, dp_same[i]+pow(2,curr_bit)*(bit_cnts[curr_bit]))
        if dp_small[i] > -1:
            dp_small[i-1] = max(dp_small[i-1], dp_small[i] + pow(2,curr_bit)*(n-bit_cnts[curr_bit]))
            dp_small[i-1] = max(dp_small[i-1], dp_small[i] + pow(2,curr_bit)*(bit_cnts[curr_bit]))


ans = max(dp_same[0],dp_small[0])
print(ans+1)

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

bit0_count = [0] * 64
bit1_count = [0] * 64

for A in map(int, input().split()):
    for i in range(64):
        if A & (1 << i):
            bit1_count[i] += 1
        else:
            bit0_count[i] += 1

ans = 0
less = -1
equal = 0
for i in range(63, -1, -1):
    if K & (1 << i):
        if less == -1:
            less = bit1_count[i] * (1 << i)
        else:
            less += max(bit0_count[i], bit1_count[i]) * (1 << i)
    
        if bit0_count[i] > bit1_count[i]:
            equal += bit0_count[i] * (1 << i)
        else:
            equal += bit1_count[i] * (1 << i)
            less = max(less, equal)
    else:
        equal += bit1_count[i] * (1 << i)
        if less != -1:
            less += max(bit0_count[i], bit1_count[i]) * (1 << i)
    
print(max(less, equal))

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

bit_cnts = [0]*41
for a in al:
    for i in range(41):
        if a&(1<<i) > 0:
            bit_cnts[i] += 1


dp_same = [-1]*42
dp_small = [-1]*42
dp_small[41] = -1
dp_same[41] = -1
for i in range(41,0,-1):
    curr_bit = i-1
    kbit = 0
    if k&(1<<curr_bit) > 0: kbit = 1
    if kbit == 0:
        dp_same[i-1] = dp_same[i] + pow(2,curr_bit)*bit_cnts[curr_bit]
        
        if dp_small[i] > -1:
            dp_small[i-1] = dp_small[i] + pow(2,curr_bit)*(n-bit_cnts[curr_bit])
            dp_small[i-1] = max(dp_small[i-1], dp_small[i] + pow(2,curr_bit)*(bit_cnts[curr_bit]))
    else:
        dp_same[i-1] = dp_same[i] + pow(2,curr_bit)*(n-bit_cnts[curr_bit])
        if dp_small[i] > -1:
            dp_small[i-1] = dp_small[i] + pow(2,curr_bit)*(n-bit_cnts[curr_bit])
            dp_small[i-1] = max(dp_small[i-1], dp_small[i] + pow(2,curr_bit)*(bit_cnts[curr_bit]))
        dp_small[i-1] = max(dp_small[i-1], dp_same[i]+pow(2,curr_bit)*(bit_cnts[curr_bit]))


ans = max(dp_same[0],dp_small[0])
print(ans+1)

Solution (Python):
import copy
N,K = map(int,input().split())
lis = list(map(int,input().split()))
final = copy.copy(lis)
count = []
ans_K = 0
ans = 0
for i in range(1,41):
    check = 0
    for j in range(N):
        if lis[j]%2 != 0:
            check += 1
        if lis[j] == 1:
            lis[j] =0
        lis[j] = lis[j]//2
    if check >= N//2 +1:
        count.append(0)
    else:
        count.append(1)
count.reverse()
for k in range(len(count)):
    if count[k] == 1:
        if ans_K +(2 ** (len(count)-k-1)) <=K:
            ans_K += 2 ** (len(count)-k-1)
for l in final:
    ans += ans_K^l
print(ans)

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

kb = 60

bits = [K]
for i in range(kb):
    if (1 << i) & K:
        bits.append((K & ~((1 << i) - 1)) - 1)


bit0_count = [0] * kb
bit1_count = [0] * kb

for A in map(int, input().split()):
    for i in range(kb):
        if A & (1 << i):
            bit1_count[i] += 1
        else:
            bit0_count[i] += 1

ans = 0
for k in bits:
    tmp = 0
    for i in range(kb):
        if k & (1 << i):
            tmp += max(bit0_count[i], bit1_count[i]) * (1 << i)
        else:
            tmp += bit1_count[i] * (1 << i)
        
    ans = max(ans, tmp)

print(ans)

Solution (Python):

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


bits = [0] * 40
for k in range(40):
    for v in X:
        bits[k] += v >> k & 1


ctr = [0] * 41
for k in range(40):
    ctr[k + 1] = ctr[k] + (max(N - bits[k], bits[k]) << k)

res = 0
cnt = 0
for i in reversed(range(40)):
    if K >> i & 1:
        res = max(res, cnt + (bits[i] << i) + ctr[i])
        cnt += (N - bits[i]) << i
    else:
        cnt += bits[i] << i

print(max(res, cnt))

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

b = [0] * 40
for i in range(40):
    for k in A:
        b[i] += (k & (1 << i)) >> i

c = [0] * 40
for i in range(39):
    if b[i] > N - b[i]:
        c[i + 1] = c[i] + (b[i] << i)
    else:
        c[i + 1] = c[i] + (N - b[i] << i)

ans = 0
cnt = 0
for i in reversed(range(40)):
    if K & (1 << i):
        ans = max(ans, cnt + (b[i] << i) + c[i])
        cnt += N - b[i] << i
    else:
        cnt += b[i] << i
print(max(ans, cnt))