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


"""
参考：https://img.atcoder.jp/abc117/editorial.pdf
・各ビット0の多い所は1にするっていう方針は合ってた。
・ちょっと条件間違って書いてたのと、
　K以下に限定する時上の桁から見てくってのが足りなかった。
"""

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, K = MAP()
aN = LIST()
Kb = format(K, 'b')
mxlen = len(Kb)

c = Counter()
for i in range(N):
    b = format(aN[i], '0' + str(mxlen) + 'b')
    b = b[::-1]
    
    for j in range(len(b)):
        if b[j] == '0':
            c[j] += 1

num = ''
for i in range(mxlen):
    
    if c[i] > N / 2:
        num = '1' + num
    else:
        num = '0' + num

X = 0
for i in range(len(num)):
    if num[i] == '1':
        
        if X + 2 ** (len(num)-i-1) <= K:
            X += 2 ** (len(num)-i-1)

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

Solution (Python):
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline
n,k = map(int,input().split())
a = list(map(int,input().split()))
bit = [0]*41
for i in range(n):
        for j in range(41):
                if a[i] & 1<<j:
                        bit[j] += 1
ans = 0
ima = 0
dp = [[0]*2 for i in range(42)]
for i in range(40,-1,-1):
    if 1<<i > k:
      dp[i][1] += dp[i+1][1]+bit[i]*(1<<i)
      continue
    if 1 & k>>i:
        dp[i][0] = dp[i+1][1]+ bit[i]*(1<<i)
        dp[i][1] = dp[i+1][1]+(n-bit[i])*(1<<i)
    else:
        dp[i][1] = dp[i+1][1] + bit[i]*(1<<i)
    if dp[i+1][0]:
           dp[i][0] = max(dp[i][0],dp[i+1][0]+max(bit[i]*(1<<i),(n-bit[i])*(1<<i)))

dai = 0
for i in range(n):
  dai += k^a[i]
print(max(dp[0][0],dai))

Solution (Python):
N,K=map(int,input().split())
A=[bin(int(i))[2:][::-1] for i in input().split()]
K2=K&((1<<20)-1)
K1=K-K2
L=[0]*41
for a in A:
    for i in range(len(a)):
        if a[i]=='1':
            L[i]+=1


K1ans=0
otherans=0
for i in range(1<<20):
    t=0
    for j in range(20):
        if i & (1<<j):
            t+=(N-L[j])*(1<<j)
        else:
            t+=(L[j])*(1<<j)
    otherans=max(otherans,t)
    if i<=K2:
        K1ans=max(K1ans,t)
K1up=0
K1down=0
for i in range(1<<20):
    t=0
    if i>(K1>>20):
        continue
    for j in range(20):
        if i & (1<<j):
            t+=(N-L[j+20])*(1<<(j+20))
        else:
            t+=(L[j+20])*(1<<(j+20))
    if i<(K1>>20):
        K1down=max(K1down,t)
    else:
        K1up=max(K1up,t)

if K1==0:
    print(K1up+K1ans)
else:
    print(max(K1up+K1ans,K1down+otherans))

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


N, K = inpl()
A = inpl()

if K == 0:
    print(sum(A))
    exit()

t = len(bin(K)) - 2
oneCounter = [0 for _ in range(t)]

sumA = 0
for a in A:
    sumA += a
    tmp = bin(a)[2:]
    
    for i, x in enumerate(reversed(tmp)):
        
        if i >= t:
            break
        elif x == "0":
            continue
        oneCounter[i] += 1
    


nibeki = [2**i for i in range(t)]
ans = sumA
orK = bin(K)[2:]

tmp = 0
for j in range(len(orK)):
    if orK[j] == "0":
        continue
    tmp += nibeki[t - 1 - j] * (N - 2 * oneCounter[t - 1 - j])
ans = max(ans, sumA + tmp)

for i in range(len(orK)):
    if orK[i] == "0":
        continue

    tmp = 0
    for j in range(i):
        if orK[j] == "0":
            continue
        tmp += nibeki[t - 1 - j] * (N - 2 * oneCounter[t - 1 - j])
    

    for j in range(i + 1, t):
        if 2 * oneCounter[t - 1 - j] < N:
            
            tmp += nibeki[t - 1 - j] * (N - 2 * oneCounter[t - 1 - j])
    
    ans = max(ans, sumA + tmp)
print(ans)

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

cnt = [0 for _ in range(40)]
for ak in a:
    i = 0
    while(ak>0):
        cnt[i] = cnt[i] + ak%2
        ak //= 2
        i += 1

kn = k+1
fmax = 0
for i in range(40):
    f = 0
    if((kn >> i) % 2 == 0 ):
        continue
    for j in range(i):
        f += 2**j * max(cnt[j], n-cnt[j])
    f += 2**i * cnt[i]
    for j in range(i+1, 40):
        if (kn >> j) %2 == 1:
            f += 2**j * (n - cnt[j])
        else:
            f += 2**j * cnt[j]
    fmax = max(f, fmax)

print(fmax)

Solution (Python):
def calc_score(now_ans, one_counter, N):
    score = 0
    length = len(one_counter)
    for i, cn in enumerate(zip(now_ans, one_counter[::-1])):
        c = cn[0]
        n = cn[1]
        point = pow(2, length - i - 1)
        if c == "0":
            score += n*point
        else:
            score += (N-n)*point
    return score


def main():
    N, K = map(int, input().split(" "))
    A = list(map(int, input().split(" ")))
    Abin = map(bin, A)
    ans_length = max(len(bin(K)), len(bin(max(A)))) - 2
    one_counter = [0 for i in range(ans_length)]
    for abin in Abin:
        rabin = abin[::-1]
        for i, c in enumerate(rabin):
            if ans_length <= i:
                break
            if c == "1":
                one_counter[i] += 1
            elif c == "b":
                break
    
    border = N/2
    temp_ans = ""
    for i, n in enumerate(one_counter[::-1]):
        if n >= border:
            temp_ans += "0"
        else:
            temp_ans += "1"

    binK = bin(K)[2:].zfill(ans_length)
    ans = calc_score(binK, one_counter, N)
    
    
    for i, c in enumerate(binK):
        if c == "0":
            continue
        now_ans = binK[:i] + "0" + temp_ans[i+1:]
        temp = calc_score(now_ans, one_counter, N)
        ans = max(ans, temp)
        
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):


import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, K = MAP()
aN = LIST()
Kb = format(K, 'b')
mxlen = len(Kb)

c = Counter()
for i in range(N):
    b = format(aN[i], 'b')
    b = b.zfill(mxlen)
    b = b[::-1]
    for j in range(len(b)):
        if b[j] == '0':
            c[j] += 1

num = ''
for i in range(mxlen):
    if c[i] > N / 2:
        num = '1' + num
    else:
        num = '0' + num

X = 0
for i in range(len(num)):
    if num[i] == '1':
        if X + 2 ** (len(num)-i-1) <= K:
            X += 2 ** (len(num)-i-1)

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

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
def f(x):
  ret = 0
  for i in range(n):
    ret += a[i]^x
  return ret

import math
if k == 0:
  print(f(0))
else:
  bit = int(math.log(k, 2))
  check= [0] * (bit + 1) 
  for i in range(bit + 1):
    check[i] = (sum([(a[j] & 2**i) // (2**i) for j in range(n)]))

  ans = [f(k)]
  for i in range(bit + 1):
    x = 0
    if k&(2**i) > 0:
      for j in range(bit + 1):
        if check[j] <= ((n-1) // 2) and j < i:
          x += 2**j
        if j > i:
          x += k&(2**j)
    ans.append(f(x))
  print(max(ans))

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

if K==0:
    ans=0
    for a in A:
        ans+=a^0
    print(a)
    exit()


l = len(bin(K))-2
s0 = [0 for i in range(l)]
s1 = [0 for i in range(l)]
for a in A:
    S = bin(a)[2:].zfill(l)
    for i in range(1,l+1):
        if S[-i]=='0':
            s0[i-1]+=1
        else:
            s1[i-1]+=1


res0 = ['0',s1[l-1]*(2**(l-1))]
res1 = ['1',s0[l-1]*(2**(l-1))]
n = l-2
Kstr=bin(K)[2:]

while n>=0:
    
    tmp0 = []
    if (res0[0]+'0').ljust(l,'0') <= Kstr:
        tmp0.append([res0[0]+'0',res0[1]+s1[n]*(2**n)])
    if (res1[0]+'0').ljust(l,'0') <= Kstr:
        tmp0.append([res1[0]+'0',res1[1]+s1[n]*(2**n)])
    tmp0.sort(key=lambda x:x[0])
    tmp0.sort(key=lambda x:x[1],reverse=True)
    nextres0 = tmp0[0]

    
    tmp1 = []
    if (res0[0]+'1').ljust(l,'0') <= Kstr:
        tmp1.append([res0[0]+'1',res0[1]+s0[n]*(2**n)])
    if (res1[0]+'1').ljust(l,'0') <= Kstr:
        tmp1.append([res1[0]+'1',res1[1]+s0[n]*(2**n)])
    tmp1.sort(key=lambda x:x[0])
    tmp1.sort(key=lambda x:x[1],reverse=True)
    res1 = tmp1[0]
    res0 = nextres0

    n-=1

res0 = int('0b'+res0[0],0)
res1 = int('0b'+res1[0],0)

ans0=sum([res0^a for a in A])
ans1=sum([res1^a for a in A])

print(max(ans0,ans1))

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





a.sort(key=lambda x:-x)
powSize=math.ceil(math.log(k+1)/math.log(2))
digitCnt=[0for _ in range(powSize)]
for i in range(n):
    for j in range(powSize):
        if ( a[i]&(1<<j) )>0:
            digitCnt[j]+=1
ansNum=[0]
for i in range(powSize-1,-1,-1):
    if 2*digitCnt[i]<n: 
        for j in range(len(ansNum)):
            ansNum[j]+=(1<<i)
            if ansNum[j]>k:
                if ( ansNum[j]&(1<<(i+1)) )>0:
                    ansNum.append(ansNum[j]-(1<<(i+1)))
                ansNum[j]-=(1<<i)
    








ans=[0for _ in range(len(ansNum))]
for i in range(n):
    for j in range(len(ansNum)):
        if ansNum[j]<=k:
            ans[j]+=(a[i]^ansNum[j])



ans.sort(key=lambda x:-x)
print(ans[0])

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

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

for a in A:
    for i in range(40):
        B[i] += (a & (1 << i)) >> i

ans = 0
s = 0
for i in range(39, -1, -1):
    if K & (1 << i) > 0:
        tmp = s
        tmp += B[i] << i
        for j in range(i-1, -1, -1):
            tmp += max(B[j], N - B[j]) << j
        ans = max(ans, tmp)
    if K & (1 << i) > 0:
        s += (N - B[i]) << i
    else:
        s += B[i] << i

ans = max(ans, s)

print(ans)

Solution (Python):
def solve(N, K, As):
    Bs = ["{0:041b}".format(a) for a in As]
    ans = ""
    for i in range(0, 41):
        ck = sum([int(b[i]) for b in Bs])
        if ck > N - ck:
            ans += "0"
        else:
            ans += "1"

    Kstr = "{0:041b}".format(K)
    d = 0
    for k in range(1, 42):
        x = Kstr[:k-1] + "0" + ans[k:]
        X = int(x, 2)
        if X <= K:
            d = max(d, sum(X ^ a for a in As))
    return d

if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    As = list(map(int, input().split(" ")))
    print(solve(N, K, As))

Solution (Python):
from collections import defaultdict

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

D = defaultdict(int)
max_bit = 1
for a in A:
    temp = a
    bit = 1
    for i in range(50):
        if temp%2==1: D[bit]+=1
        temp//=2
        bit*=2
        if temp==0:break
    i+=1
    if i > max_bit: max_bit=i

KD = defaultdict(int)
temp = K
k_bit = 1
for i in range(50):
    if temp%2==1:KD[k_bit]+=1
    temp//=2
    k_bit*=2
    if temp==0:break
k_bit = i+1
            
SD = {}
SDD = []
d = 1
for i in range(max(max_bit,k_bit)):
    
    SD[d] = [d*(D[d]),d*(N-D[d])]
    if len(SDD)==0:
        SDD.append(max(SD[d]))
    else:
        SDD.append(SDD[i-1]+max(SD[d]))
    d*=2





allANS = []
ans = 0
p = pow(2,k_bit)
for i in range(k_bit,max_bit):
    ans += SD[p][0]
    p*=2
    
p = int(pow(2,k_bit-1))
for i in range(k_bit)[::-1]:
    if p==0:break
    if KD[p]>0:
        if i>0: 
            allANS.append(ans+SD[p][0]+SDD[i-1]) 
        else:
            allANS.append(ans+SD[p][0])
        ans += SD[p][1]
    else:
        ans += SD[p][0]
    p//=2
    
allANS.append(ans)


print(max(allANS))

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

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

bin_K = '{:040b}'.format(K)
bin_A = ['{:040b}'.format(a) for a in A]
counter = [{'0': 0, '1': 0} for i in range(40)]
for ba in bin_A:
    for i in range(40):
        counter[i][ba[i]] += 1

cand = []
for i in range(40):
    if counter[i]['0'] < counter[i]['1']:
        cand.append('0')
    else:
        cand.append('1')

i = 0
for i in range(40):
    if bin_K[i] == '1':
        break

bin_K = bin_K[i:]
cand = cand[i:]
counter = counter[i:]

candidate = [f(0), f(K)]
for i in range(len(cand)):
    if bin_K[i] == '1':
        tmp = cand[i:]
        tmp[0] = '0'
        candidate.append(f(int(bin_K[:i]+''.join(tmp), 2)))

print(max(candidate))

Solution (Python):
n,k = map(int,input().split())
a = [int(i) for i in input().split()]
ans = sum(a)
b = [0 for i in range(41)]
for j in range(41):
    for i in range(len(a)):
        if a[i]%2==1 : b[j]+=1
        a[i]//=2
c = 40
if k==0 : c = -1
while c>=0:
    if 2**(c)>k :
        c-=1
        continue;
    if b[c] < n-b[c]:
        k-=2**c
        ans -=b[c]*2**c
        ans += (n-b[c])*2**c
    c-=1
print(ans)

Solution (Python):
def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]


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

kb = format(K, 'b')[::-1]
l = len(kb)

ab = [""]*(N)
for i in range(N):
    ab[i] = format(A[i], 'b').zfill(l)[::-1]

res = 0
for i in reversed(range(l)):
    cnt = 0
    for e in ab:
        if e[i] == '0':
            cnt += 1

    if cnt > N // 2 and res + 2 ** i <= K:
        res += 2 ** i


ans = 0
for e in A:
    ans += res ^ e
print(ans)

Solution (Python):
N, K = (int(i) for i in input().split())
K = format(K,'b').zfill(40) 
A = [int(i) for i in input().split()]
A = [format(a,'b').zfill(40) for a in A]
C = [0]*40
for i in range(40):
    cc = 0
    for a in A:
        keta = 39 - i
        if a[keta] == "1":
            cc += 1
    C[keta] = cc
anslis = []
ans = 0
for i in range(40):
    iketa = 39 - i
    if K[i] == "1":
        tempans = ans
        for j in range(i, 40):
            jketa = 39 - j
            if i == j:
                tempans += C[j] * 2**jketa
            else:
                tempans += max(C[j], N-C[j]) * 2**jketa
        anslis.append(tempans)
        ans += (N-C[i]) * 2**iketa
    else:
        ans += C[i] * 2**iketa
anslis.append(ans)
print(max(anslis))

Solution (Python):
import math
n,k = map(int,input().split())
a_list = [i for i in map(int,input().split())]
cnt_list = [0 for i in range(40)]
maxi = 0
if k == 0:
    maxi = sum(a_list)
else:
    for i in a_list:
        b = bin(i)[2:]
        b = b[::-1]
        for index,j in enumerate(b):
            cnt_list[-(index+1)] += int(j)
    goukei = 0
    for i in range(40):
        if cnt_list[i] <= n/2 and (goukei + 2**(39-i)) <= k:
            goukei += 2**(39-i)
            maxi += (2**(39-i)) * (n - cnt_list[i])
        else:
            maxi += (2**(39-i)) * (cnt_list[i])

print(maxi)

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

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

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

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

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

MB = 50

bits = [0] * (MB + 1)

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



def calc(k):
    r = 0
    for j in range(0, MB):
        if k & (1 << j):
            r += max(bits[j], N - bits[j]) << j
        else:
            r += bits[j] << j
    return r

result = calc(K)

for i in range(0, MB):
    m = 1 << i
    if K & m:
        k = K ^ m | (m - 1)
        r = calc(k)
        
        result = max(result, r)

print(result)

Solution (Python):

from pprint import pprint as pp
N, K = map(int, input().split())
An = list(map(int, input().split()))

bin_cnt = [[0 for _ in range(N)] for _ in range(40)]

for i in range(N):
    tmp = An[i]
    for j in range(40):
        bin_cnt[j][i] = tmp%2
        tmp = tmp//2

X = 0
for j in sorted(range(40),reverse=True):
    if sum(bin_cnt[j]) < N - sum(bin_cnt[j]):
        X += 2**j
    if X > K:
        X -= 2**j

ans = 0


for A in An:
    ans += X^A

print(ans)

Solution (Python):
n,m = map(int,raw_input().split())
q = map(int,raw_input().split())

bit = [0]*40

for a in q:
  buf = a
  for b in range(40):
    bit[b] += buf & 1
    buf >>= 1

ans = 0
now = 0

for b in range(39,-1,-1):
  qq = 1<<b
  if (now+qq) > m:
    ans += (1<<b)*bit[b]
    continue
  if bit[b] > (n/2):
    ans += (1<<b)*bit[b]
  else:
    ans += (1<<b)*(n-bit[b])
    now += qq

print ans

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


N, K = [int(elem) for elem in fin().split()]
A_list = [int(elem) for elem in fin().split()]
assert len(A_list) == N

n_digits_K = 0
cur_K = K
while cur_K > 0:
    n_digits_K += 1
    cur_K >>= 1


count_1_by_digit = [0] * n_digits_K
for A in A_list:
    i = 0
    while A > 0 and i < len(count_1_by_digit):
        count_1_by_digit[i] += A & 1
        i += 1
        A >>= 1


should_up = [i for i, count in enumerate(count_1_by_digit) if count <= (N - 1) // 2]
should_up.append(-1)
max_f = 0

for down_digit in should_up:
    X = 0
    for i in reversed(range(len(count_1_by_digit))):
        count = count_1_by_digit[i]
        if count <= (N - 1) // 2 and i != down_digit:  
            X += (1 << i)
            if X > K:
                X -= (1 << i)
    
    
    f = 0
    for A in A_list:
        f += A ^ X
    max_f = max(max_f, f)

print(max_f)

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

bn = bin(k)[2:]
l = 0
ba = []
for i in range(n):
    ba.append(bin(a[i])[2:])
    l = max(len(ba[i]), l)
l = max(l, len(bn))
bn = bn.zfill(l)
ba = [ba[i].zfill(l) for i in range(n)]

c = [0]*l
for a in ba:
    for i in range(l):
        if a[i] == "1": 
            c[i] += 1
ans = 0
x = 0


for i in range(l):
    if k >= x + 2**(l-i-1):
        if c[i] >= n/2:
            ans += (2**(l-i-1)) * c[i]
        else:
            ans += (2**(l-i-1)) * (n-c[i])
            x += 2**(l-i-1)
    else:
        ans += (2**(l-i-1)) * c[i]
    
print(ans)

Solution (Python):
from itertools import accumulate

n, k = list(map(int, input().split()))
aaa = list(map(int, input().split()))
bk = '{:041b}'.format(k)
bbb = list(map('{:041b}'.format, aaa))
ks = 0
best = []
thr = []
base = []
for i, c in enumerate(bk):
    d = 1 << (40 - i)
    c1 = list(b[i] for b in bbb).count('1')
    d0, d1 = c1 * d, (n - c1) * d
    best.append(max(d0, d1))
    thr.append(d0 if c == '0' else d1)
    base.append(d0)

best.reverse()
best = list(accumulate(best))
best.reverse()
best.append(0)
thr = list(accumulate(thr))

ans = thr[-1]
for i, c in enumerate(bk):
    if c == '0':
        continue
    ans = max(ans, thr[i - 1] + base[i] + best[i + 1])

print(ans)

Solution (Python):
def solve():
  N, K = map(int, input().split())
  A = [int(i) for i in input().split()]
  B = [0] * 40
  for i in range(40):
    for a in A:
      if a & (1 << i): B[i] += 1

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

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

  return ans

print(solve())

Solution (Python):
n, k = [int(i) for i in input().split()]
As = [int(i) for i in input().split()]
def func(x):
    return sum(a^x for a in As)

bs = ['{:050b}'.format(a)[::-1] for a in As]

strk = '{:b}'.format(k)

ans = ['0'] * len(strk)

for i in range(len(strk)):
    one = len([True for b in bs if b[len(strk) - 1 - i] == '1'])
    zero = len([True for b in bs if b[len(strk) - 1 - i] == '0'])
    

    tmp = ans[:]
    

    
    
    if zero >= one:
        tmp[i] = '1'
    
    
    
    if k >= int(''.join(tmp), 2):
        ans = tmp
    

print(func(int(''.join(ans), 2)))

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

"""
方針　各桁を0にするか1にするかは独立に考えてよい
 
K = 10101 の時
0か1か好きに選べる桁をfとして
* X = 10101
* X = 10100
* X = 100ff
* X = 0ffff
を試し、最大になるものを選ぶ
 
2**39 < 10**12 < 2**40　なので40桁について考え
fのときどっちを選ぶとよいかを前計算しておく
""" 
 
L = [0]*40  
for i in range(N):
    for j in range(40):
        L[j] += (A[i] >> j)&1
 
default = [(N - L[i]) * (2**i) if (K>>i)&1 == 1 else L[i] * (2**i) for i in range(40)]
free = [max(L[i] * (2**i), (N-L[i])*(2**i)) for i in range(40)]
 
ans = sum([K^A[i] for i in range(N)])
for i in range(40):
    if (K >> i)&1 == 1:
        ans = max(ans,
                  sum(free[:i]) + L[i]*(2**i) + sum(default[i+1:]))
print(ans)

Solution (Python):



from collections import Counter

def main():
    n, k = list(map(int, input().split()))
    As = list(map(int, input().split()))
    ans = 0
    x = 0
    for i in range(43, -1, -1):
        pow2i = 1 << i
        c = 0
        for a in As:
            if (a >> i) & 1:
                c += 1
        if n - c > c and x + pow2i <= k:
            ans += (n - c) * pow2i
            x += pow2i
        else:
            ans += c * pow2i
    print(ans)



if __name__ == '__main__':
    main()

Solution (Python):
n,k=map(int,input().split())
A=list(map(int,input().split()))
ones=[0]*40
for a in A:
    for i in range(40):
        if a&(1<<i):
            ones[i]+=1
x=0
for i in range(39,-1,-1):
    if x+(1<<i)>k:
        continue
    elif ones[i]<n-ones[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 = a.copy()
count = 1
d = 1
while k >= d:
    count += 1
    d *= 2
else:
    count -= 1
    d //= 2
anst = 0
for i in range(count):
    level = 0
    for j in range(n):
        tmpb = b[j] // d
        if tmpb >= 1 and tmpb % 2 == 1:
            level += 1
        b[j] %= d
    if k >= anst + d and n > level * 2:
        anst += d
    d //= 2

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

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

    r = 1
    X = 0
    
    while (r <= K):
        r *= 2
    
    while (0 < r):
        count = 0
        for a in A:
            if (0 < (r & a)):
                count += 1
        
        if (N//2 >= count):
            if ((X+r) <= K):
                X += r
        
        r //= 2
    
    res = 0
    for a in A:
        res += X ^ a
    print(res)
main()

Solution (Python):

from functools import reduce
from math import log2
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def floor(x, y):
    return int((-x)//y*(-1))


def floorlog(x):
    if x > 0:
        return floor(log2(x), 1)
    else:
        return 0


def XXor(X, A):
    
    return X ^ A


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


def xorSum(X):
    ret = 0
    for a in A:
        ret += XXor(X, a)
    return ret


def solve():

    ans = 0
    ans_x = 0
    for x in range(K+1):
        tmp = xorSum(x)
        if tmp > ans:
            ans = tmp
            ans_x = x
    

    return ans


def solve2():
    ans = 0
    for i in reversed(range(0, 40)):
        b = sum([(a >> i) % 2 for a in A])*2 < N
        if b and ans+(1 << i) <= K:
            ans += (1 << i)
        else:
            continue
    return xorSum(ans)


print(solve2())

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
bit = [0]*64
  
for i in range(n):
    for j in range(60):
        if a[i]>>j & 1:
            bit[j] += 1
 
x = 0
for i in range(59,-1,-1):
    if bit[i] < n-bit[i] and x + (1<<i) <= k:
        x += 1<<i
sum = 0
for i in range(n):
    sum += a[i]^x
print(sum)

Solution (Python):
from sys import stdin
n, k = map(int, stdin.readline().rstrip().split())
a = [format(int(x), 'b')[::-1] for x in stdin.readline().rstrip().split()]

d = [0] * 64
maxlen = 0
for c in a:
    len_ = len(c)
    if len_ > maxlen:
        maxlen = len_
    for j in range(len(c)):
        if c[j] == '1':
            d[j] += 1

m = format(k, 'b')[::-1]
if len(m) >= maxlen:
    maxlen = len(m)
else:
    m = m + '0' * (maxlen - len(m))

flag = False
result = 0
for j in range(maxlen - 1, -1, -1):
    if d[j] >= n - d[j]:
        result = result * 2 + d[j]
        if m[j] == '1':
            flag = True
    else:
        if flag or m[j] == '1':
            result = result * 2 + n - d[j]
        else:
            result = result * 2 + d[j]

print(result)

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

binK = bin(K)[2:]
maxbinAsize = 0
ans = 0
B = [0 for _ in [0]*40]

for i in range(N):
    binA = bin(A[i])[2:][::-1]
    maxbinAsize = max(maxbinAsize,len(binA))
    for j in range(len(binA)):
        B[j] = B[j] + int(binA[j])
        
SearchRange = max(len(binK),maxbinAsize)
index = [int(t < N/2) for t in B[:len(binK)][::-1]]

for k in range(SearchRange):
    if k < len(binK):
        ans = ans + max(B[k], N-B[k])*(2**k)
    else:
        ans = ans + B[k]*(2**k)

for l in range(len(binK)):
    if int(binK[l]) > index[l]:
        break
    if int(binK[l]) < index[l]:
        ll = len(index) - l - 1
        ans = ans - abs(N - 2 * B[ll])*(2**ll)
            
print(ans)

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
 
c=[[0 for _ in range(2)] for _ in range(64)]
 
for i in range(n):
    for j in range(60):
        c[j][a[i]>>j&1] += 1
x=0
for i in range(59,-1,-1):
    if(c[i][0] > c[i][1] and x+(1<<i) <= k):
        x += 1<<i
 
sum = 0
for i in range(n):
    sum += a[i]^x
print(sum)

Solution (Python):

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

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

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

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

print(ans)

Solution (Python):
import math
def main():
  N, K = list(map(int, input().split()))
  A = list(map(int, input().split()))
 
  if K == 0:
    C = 0
  else:
    C = int(math.log2(K + 1))
  L = [[0 for i in range(44)] for j in range(C + 1)]
 
  for i in A:
    for j in range(len(L[0])):
      if i % 2 == 1:
        i -= 1
        L[0][j] += 1
      if i == 0:
        break
      i /= 2
  for i in range(1, C + 1):
    for j in range(44):
      L[i][j] = L[0][j]
 
  x = pow(2, C)
  T = [K for i in range(C + 1)]
  for i in range(C, -1, -1):
    for j in range(C + 1):
      if T[j] >= x:
        if j != i and L[j][i] <= N / 2:
          L[j][i] = N - L[j][i]
          T[j] -= x
    x //= 2
 
  Ans = [0 for i in range(C + 1)]
  x = 1
  for i in range(44):
    for j in range(C + 1):
      Ans[j] += L[j][i] * x
    x *= 2
 
  print(max(Ans))

main()

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

a_2 = []

if k == 0:
    print(sum(a))
    exit()

for i in range(n):
    a_2.append(list(format(a[i], '

a_bit = len(bin(max(a))) - 2
k_bit = len(bin(k)) - 2

X = ''

for i in range(40 - k_bit, 40):
    cnt1 = 0
    for j in range(n):
        if a_2[j][i] == '1':
            cnt1 += 1

    if cnt1 >= (n + 1) // 2:
        X += '0'
    else:
        if 40 - i <= 2:
            s = X + '1' * (40 - i)
        else:
            s = X + '1' + '0' * (40 - i - 1)

        if s == '':
            X += '1'
        elif int(s, 2) > k:
            X += '0'
        else:
            X += '1'

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

print(ans)

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
t,ans=2**40,0
while t:
	c=sum([(a[i]&t)//t for i 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):
import math
import copy
import bisect








def nCast(number):
    if type(number)==str:
        return int(number)
    for idx in range(0,len(number)):
        if type(number[idx])==str:

            number[idx]=int(number[idx])
        else:
            nCast(number[idx])
    return number
    
def inputArr(w):
    l=list()
    for idx in range(0,w):
        l.append(input())
    return l
def inputArr1(w):
    l=list()
    for idx in range(0,w):
        l.append(input().split())
    return l

n=nCast(input().split())
a=nCast(input().split())

def myKey(a):
    return a[0]


def func():
    base=1<<64
    
    tag=True
    
    number=0

    while base!=0:
        if tag and n[1]&base!=0:
           
            one =0
            zero=0
            for idx in range(0,len(a)):
                if base&a[idx]!=0:
                    one+=1
                else:
                    zero+=1

            if one>=zero:
                tag=False
            else:
                
                number+=base
        elif not tag:
            one =0 
            zero=0
            for idx in range(0,len(a)):
                if base&a[idx]!=0:
                    one+=1
                else:
                    zero+=1
            if one<zero:
                
                number+=base
        base=base>>1
 
    result=0
    
    for idx in range(0,len(a)):
        result+=number^a[idx]
    return result
    
    
    
    
print(func())