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

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

k_bin = "{:040b}".format(k)
A_bin = list(map(lambda x: '{:040b}'.format(x), A))
X = ''
first = 1
for i, col in enumerate(zip(*A_bin)):
    if k_bin[i] == '0' and first:
        X += '0'
        continue
    if first:
        zero_cnt = col.count('0')
        one_cnt = n-zero_cnt
        if one_cnt < zero_cnt:
            X += '1'
        else:
            first = 0
            X += '0'
        continue

    zero_cnt = col.count('0')
    one_cnt = n-zero_cnt
    if one_cnt < zero_cnt:
        X += '1'
    else:
        X += '0'

X = int(X, 2)

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

Solution (Python):
import sys
import numpy as np
N, K = map(int, sys.stdin.readline().rstrip().split())
A = np.array(list(map(int, sys.stdin.readline().rstrip().split())))
cnt = []

for i in range(41):
    cnt.append(np.count_nonzero(A >> i & 1))

cnt = cnt[::-1]
dp = [[0] * 2 for _ in range(42)]
ans = 0
base = 2**(41 - 1)

for i, c in enumerate(cnt, 1):
    if K >> (41 - i) & 1 == 1:
        dp[i][0] = dp[i - 1][0] + base * (N - c)
        if dp[i - 1][1] > 0:
            dp[i][1] = max(dp[i - 1][0] + base * c, dp[i - 1][1] + base * c,
                           dp[i - 1][1] + base * (N - c))
        else:
            dp[i][1] = dp[i - 1][0] + base * c

    else:
        dp[i][0] = dp[i - 1][0] + base * c
        if dp[i - 1][1] > 0:
            dp[i][1] = max(dp[i - 1][1] + base * c,
                           dp[i - 1][1] + base * (N - c))

    base //= 2

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

Solution (Python):
def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N, K = ZZ()
    A = ZZ()
    if K == 0:
        print(sum(A))
        return

    bK = format(K, 'b')
    msb = len(bK)
    plus = [0] * msb

    for a in A:
        for i, b in enumerate(format(a, '0{}b'.format(msb))[::-1][:msb]): plus[i] += int(b)
    e = 1
    for i in range(msb):
        plus[i] = e * (N - 2 * plus[i])
        e *= 2

    dp = [[0] * 2 for _ in range(msb)]
    dp[0][0] = plus[i]
    plus = plus[::-1]

    for i in range(msb-1):
        dp[i+1][0] = max(dp[i+1][0], dp[i][0] + plus[i+1] * int(bK[i+1]))
        if int(bK[i+1]) == 1: dp[i+1][1] = max(dp[i+1][1], dp[i][0])
        dp[i+1][1] = max(dp[i+1][1], dp[i][1], dp[i][1] + plus[i+1])
    print(max(dp[msb-1]) + sum(A))

    return

if __name__ == '__main__':
    main()

Solution (Python):
import sys
N, K = map(int, sys.stdin.readline().rstrip().split())
A = list(map(int, sys.stdin.readline().rstrip().split()))
bin_k = bin(K)[2:].zfill(50)
cnt = [0] * 50

for a in A:
    bin_a = bin(a)[2:]
    for i, b in enumerate(bin_a[::-1]):
        if b == "1":
            cnt[i] += 1

cnt = cnt[::-1]
dp = [[0] * 2 for _ in range(50 + 1)]
ans = 0
base = 2 ** (50 - 1)
flag = False

for i, c in enumerate(cnt, 1):
    if flag:
        if bin_k[i - 1] == "1":
            dp[i][0] = dp[i - 1][0] + base * (N - c)
            dp[i][1] = max(dp[i - 1][0] + base * c, dp[i - 1][1] + base * c,
                        dp[i - 1][1] + base * (N - c))
        else:
            dp[i][0] = dp[i - 1][0] + base * c
            dp[i][1] = max(dp[i - 1][1] + base * c, dp[i - 1][1] + base * (N - c))
    else:
        if bin_k[i - 1] == "1":
            dp[i][0] = dp[i - 1][0] + base * (N - c)
            tmp1 = dp[i - 1][0] + base * c
            tmp2 =  dp[i - 1][1] + base * c
            tmp3 = dp[i - 1][1] + base * (N - c)
            if tmp3 <= tmp1 and tmp3 <= tmp2:
                dp[i][1] = max(tmp1, tmp2)
                flag = True
            elif tmp3 <= tmp1:
                dp[i][1] = tmp1
                flag = True
            else:
                dp[i][1] = tmp3
        else:
            dp[i][0] = dp[i - 1][0] + base * c
            dp[i][1] = dp[i - 1][1] + base * c

    base //= 2

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

Solution (Python):
import sys
import math
N, K = map(int, sys.stdin.readline().rstrip().split())
A = list(map(int, sys.stdin.readline().rstrip().split()))
bin_k = bin(K)[2:].zfill(50)
cnt = [0] * 50

for a in A:
    bin_a = bin(a)[2:]
    for i, b in enumerate(bin_a[::-1]):
        if b == "1":
            cnt[i] += 1

cnt = cnt[::-1]

ans = 0
base = 2**(50 - 1)
flag = False
for i, c in enumerate(cnt):
    if flag:
        ans += base * max(c, N - c)
    else:
        if bin_k[i] == "1":
            if c >= N - c:
                ans += base * c
                flag = True
            else:
                ans += base * (N - c)

        else:
            ans += base * c
    base //= 2
print(ans)

Solution (Python):


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

cnts = [0] * 46

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

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

for i in range(L):
    
    p0 = pow(2, L-1 - i) * cnts[L-1-i]
    p1 = pow(2, L-1 - i) * (N - cnts[L-1-i])

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


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

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

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



print(max(dp[-1]))

Solution (Python):
n,k=map(int,input().split())
A=list(map(int,input().split()))
B=[0]*40
for i in A:
  s=format(i,"40b")
  for j in range(40):
    if s[-1-j]=="1":
      B[j]+=1
C=[0]*40
for i in range(40):
  if B[-1-i]<n/2:
    C[i]=1
  else:
    C[i]=0
AA=[]
a=0
for i in range(40):
  if C[i]==1:
    if a+2**(39-i)>k:
      continue
    b=a
    for j in range(i+1,40):
      if C[j]==1:
        b=b+2**(39-j)
    AA.append(b)
    a=a+2**(39-i)
AA.append(a)
ans=0
for i in AA:
  a=0
  for j in A:
    a=a+(i^j)
  if a>ans:
    ans=a
print(ans)

Solution (Python):

import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *





































def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007




def main():
	N,K = inputMap()
	A = inputList()

	marks = bin(K)[2:]
	marks = marks[::-1]
	tmp = len(marks)
	for i in range(tmp,40):
		marks += "0"
	marks = marks[::-1]

	touhyou = [0 for i in range(40)]
	for i,val in enumerate(A):
		bin_str = bin(val)[2:]
		bin_str = bin_str[::-1]
		
		for j,vol in enumerate(bin_str):
			if "1" == vol:
				touhyou[j] += 1

	smp = ""
	hofe = N // 2
	
	for i, val in enumerate(touhyou):
		if int(val) > hofe:
			smp += "0"
		else:
			smp += "1"

	smp = smp[::-1]
	
	

	masksss = []
	tmp = ""
	onyour = ""
	for i in range(40):
		if marks[i] == "0":
			tmp += "0"
		else:
			onyour = tmp + "1"
			tmp += "0"
			for j in range(i+1,40):
				tmp += "1"
			masksss.append(tmp)
			break

	while True:
		if len(onyour) == 40:
			break

		for i in range(len(onyour),40):
			if marks[i] == "1":
				tmp = onyour + "0"
				for j in range(i+1,40):
					tmp += "1"
				masksss.append(tmp)
				onyour += "1"
			else:
				onyour += "0"

	masksss.append(onyour)

	ans = 0
	for i in masksss:
		tmp = int(i,2) & int(smp,2)
		tmptmp = 0
		for vol in A:
			tmptmp += tmp ^ vol

		
		if ans < tmptmp:
			ans = tmptmp

	print(ans)
	






def bisect_left_reverse(a, x):
    if a[0] <= x:
        return 0
    if x < a[-1]:
        return len(a)
    
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] <= x:
            ok = mid
        else:
            ng = mid
    return ok

def bisect_right_reverse(a, x):
    if a[0] < x:
        return 0
    if x <= a[-1]:
        return len(a)
    
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] < x:
            ok = mid
        else:
            ng = mid
    return ok





def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) //2
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid -1
        else:
            low = mid + 1
    return None




def sunuke(N, K, mod=10**9+7):
	if N < K or K-1 < 0:
		return 0
	else:
		return combination(N-1, K-1, mod)




def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res


def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y




def H(n, r, mod=10**9+7):
	
	
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        
        
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv



def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)



if __name__ == "__main__":
	main()

Solution (Python):





N,K = map(int, input().split())
A = list(map(int, input().split()))
L = 46
cnt = [0] * L

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



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

for i in range(L):

    p0 = pow(2, L-1 - i) * cnt[L-1 - i]
    p1 = pow(2, L-1 - i) * (N - cnt[L-1 - i])

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

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

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

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


print(max(dp[-1]))

Solution (Python):
n,k = map(int,input().split())
a = list(map(int,input().split()))
l = max(len(bin(k)[2:]),len(bin(max(a))[2:]))
c = [0]*l

for i in a:
    b_a = bin(i)[2:].zfill(l)
    for j in range(l):
        if b_a[j]=='1':
            c[j] += 1

x = 0
for i in range(l):
    e = l-i-1
    if n-c[i]>c[i] and x+2**e<=k:
        x += 2**e

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

MAX_DIGIT = 40

dp = [[-1, -1] for _ in range(MAX_DIGIT+1)]
dp[0][0] = 0
for i in range(MAX_DIGIT):
    mask = 1 << (MAX_DIGIT - i - 1)
    cnt_1 = 0
    for v in a:
        if v & mask:
            cnt_1 += 1
    cnt_0 = n - cnt_1

    cost_0 = mask * cnt_1
    cost_1 = mask * cnt_0

    if dp[i][1] != -1:
        dp[i+1][1] = max(dp[i+1][1], dp[i][1] + max(cost_0, cost_1))

    if k & mask:
        dp[i+1][1] = max(dp[i+1][1], dp[i][0] + cost_0)

    if k & mask:
        dp[i+1][0] = max(dp[i+1][0], dp[i][0] + cost_1)
    else:
        dp[i+1][0] = max(dp[i+1][0], dp[i][0] + cost_0)

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

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

MAX_DIGIT = 40

dp = [[-1, -1] for _ in range(MAX_DIGIT+1)]
dp[0][0] = 0
for i in range(MAX_DIGIT):
    mask = 1 << (MAX_DIGIT - i - 1)
    cnt_1 = 0
    for v in a:
        if v & mask:
            cnt_1 += 1
    cnt_0 = n - cnt_1

    cost_0 = mask * cnt_1
    cost_1 = mask * cnt_0

    if dp[i][1] != -1:
        dp[i+1][1] = max(dp[i+1][1], dp[i][1] + max(cost_0, cost_1))


    if k & mask:
        dp[i+1][1] = max(dp[i+1][1], dp[i][0] + cost_0)


    if k & mask:
        dp[i+1][0] = max(dp[i+1][0], dp[i][0] + cost_1)
    else:
        dp[i+1][0] = max(dp[i+1][0], dp[i][0] + cost_0)

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

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

MAX_DIGIT = 40

dp = [[-1, -1] for _ in range(MAX_DIGIT+1)]
dp[0][0] = 0
for i in range(MAX_DIGIT):
    mask = 1 << (MAX_DIGIT - i - 1)
    cnt_1 = 0
    for v in a:
        if v & mask:
            cnt_1 += 1
    cnt_0 = n - cnt_1

    cost_0 = mask * cnt_1
    cost_1 = mask * cnt_0

    if dp[i][1] != -1:
        dp[i+1][1] = max(dp[i+1][1], dp[i][1] + max(cost_0, cost_1))

    if dp[i][0] != -1:
        if k & mask:
            dp[i+1][1] = max(dp[i+1][1], dp[i][0] + cost_0)
    
    if dp[i][0] != -1:
        if k & mask:
            dp[i+1][0] = max(dp[i+1][0], dp[i][0] + cost_1)
        else:
            dp[i+1][0] = max(dp[i+1][0], dp[i][0] + cost_0)

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

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
M = 50
l = len(str(N))
dp = [[-1] * 2 for _ in range(M + 1)]
dp[0][0] = 0
for i in range(M):
    mask = 1 << (M - i - 1)
    num = 0
    for j in range(N):
        if A[j] & mask:
            num += 1
    c0 = mask * num
    c1 = mask * (N - num)
    if dp[i][1] != -1:
        dp[i + 1][1] = max(dp[i + 1][1], dp[i][1] + max(c0, c1))
    if dp[i][0] != -1:
        if K & mask:
            dp[i + 1][1] = max(dp[i + 1][1], dp[i][0] + c0)
            dp[i + 1][0] = max(dp[i + 1][0], dp[i][0] + c1)
        else:
            dp[i + 1][0] = max(dp[i + 1][0], dp[i][0] + c0)
print(max(dp[M][0], dp[M][1]))

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





cnt=[0]*len(str(bin(k))[2:])



for item in a:
    for j in range(min(len(str(bin(item))[2:]),len(str(bin(k))[2:]))):
        if item>>j &1:
            cnt[j]+=1

cnt=cnt[::-1]
result=0
for index,item in enumerate(cnt):
    
    if item%2==0 and item==n//2:
        result+=0*(2**(len(cnt)-index-1))
    elif item<=n//2 and result+2**(len(cnt)-index-1)<=k:
        result+=2**(len(cnt)-index-1)
    else:
        result+=0*(2**(len(cnt)-index-1))
    

ans=0
for item in a:
    
    ans=ans+(item^result)
    
print(ans)





"""
001(1)
100(4)
101(5)

110(6)
100(4)
010(2)

011(3)
100(4)
111(7)
"""

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

i = 1
while i <= K:
  i *= 2

x = 0
while i != 0:
  if sum([1 for a in A if a&i==0]) > N/2:
    if x+i <= K:
      x += i
  i //= 2;

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

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

    ctr = [0] * 60

    for x in A:
        *bit, = map(int, bin(x)[2:])
        bit.reverse()
        for j, b in enumerate(bit):
            i = (60 - 1) - j
            ctr[i] += b

    ans = 0
    d = 1 << (60 - 1)
    x = 0
    for j, cnt in enumerate(ctr):
        if (cnt < N - cnt) and (x + d <= K):  
            x += d
            ans += (N - cnt) * d
        else:
            ans += cnt * d
        d >>= 1
    print(ans)


if __name__ == '__main__':
    main()

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

    def bit60(x):
        *bit, = map(int, bin(x)[2:])
        zfill = 60 - len(bit)
        ret = [0] * zfill
        ret += bit
        return ret

    

    ctr = [0] * 60
    for bit in map(bit60, A):
        for j in range(60):
            ctr[j] += bit[j]

    ans = 0
    d = 1 << (60 - 1)
    x = 0
    for j in range(60):
        if (ctr[j] < N - ctr[j]) and (x + d <= K):  
            x += d
            ans += (N - ctr[j]) * d
        else:
            ans += ctr[j] * d
        d >>= 1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

import sys
input = sys.stdin.readline









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


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



X = [0]*40
for i in range(40):
    if B[i] <= N/2:
        X[i] = 1


bitK = list(map(int, list(bin(K)[2:].zfill(40)[::-1])))


ans = 0
for i in range(40):
    if bitK[i]==1:
        ans += (N-B[i])<<i
    else:
        ans += B[i]<<i


for k in range(40):
    
    if bitK[k]==0:
        continue

    total = 0
    leqK = False 
    for i in range(39,-1,-1):
        
        if leqK:
            if X[i]==1:
                total += (N-B[i])<<i
            else:
                total += B[i]<<i
        
        else:
            
            if i==k:
                total += B[i]<<i
                leqK = True
            
            else:
                if bitK[i]==1:
                    total += (N-B[i])<<i
                else:
                    total += B[i]<<i
    ans = max(total,ans)

print(ans)

Solution (Python):

MAX_DIGIT = 40
SMALL = 0
EQUAL = 1
N, K = map(int, input().split())
A = list(map(int, input().split()))

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

for d in range(MAX_DIGIT):
    shift = MAX_DIGIT - d - 1
    bit_count = 0
    for a in A:
        if a >> shift & 1:
            bit_count += 1

    cost0 = (1 << shift) * bit_count
    cost1 = (1 << shift) * (N - bit_count)

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

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

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

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

Solution (Python):
import sys
from itertools import accumulate
sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    ans = list(accumulate(A))[-1]

    B = [0 for _ in range(52)]
    for i in reversed(range(51)):
        cnt1 = 0
        for j in range(n):
            if A[j] & (1 << i):
                cnt1 += 1

        cnt0 = n - cnt1
        if cnt0 > cnt1:
            B[i] = (1 << i) * (cnt0 - cnt1)

    pre = 0
    maxV = 0

    for i in reversed(range(51)):
        if k & (1 << i):
            total = 0
            for j in range(i):
                total += B[j]
            total += pre
            maxV = max(maxV, total)
            pre += B[i]

    maxV = max(maxV, pre)
    print(ans + maxV)


if __name__ == '__main__':
    resolve()

Solution (Python):
n,K=map(int,input().split())
a=list(map(int,input().split()))
c=[0]*40
ans=0

for aa in a:
  for k in range(40):
    if aa&(1<<k):c[k]+=1
x=0
for k in range(39,-1,-1):
  if x+(1<<k)>K:continue
  if c[k]<=n-c[k]:x+=(1<<k)

for aa in a:
  ans+=x^aa

print(ans)

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

A = list(map(int,input().split()))
MAX = max(max(A),K)
l = len(str(bin(MAX)))-2

AB = []
for i in range(N):
  s = str(bin(A[i]))
  temp = s[2:]
  lendif = l - len(temp)
  while lendif > 0:
    temp = "0"+temp
    lendif -= 1
  AB.append(temp)


ans = 0
now = 0 
for i in range(l): 
  
  c = 0; d = 0
  for j in range(N):
    if AB[j][i] == "0":
      c += 1
    else:
      d += 1
  if c > d: 
    if pow(2,l-1-i)+now > K:
      m = d
    else:
      now += pow(2,l-1-i)
      m = c
  else:
    m = d
  
  ans += pow(2,l-1-i)*m
print(ans)

Solution (Python):
import sys
from heapq import heappush, heappop
def input(): return sys.stdin.readline().strip()


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    if K == 0:
        print(sum(A))
        return
    
    bitK = bin(K)[2:]
    l = len(bitK)
    tight = True
    X = 0
    for n in range(l):
        one_num = 0
        for a in A:
            if a & (1 << (l - 1 - n)): one_num += 1
        if one_num > N - one_num: 
            if bitK[n] == "1":
                tight = False
                X = X * 2
            else:
                X = X * 2
        elif one_num < N - one_num: 
            if bitK[n] == "1":
                X = X * 2 + 1
            elif tight:
                X = X * 2
            else:
                X = X * 2 + 1
        else: 
            if bitK[n] == "1":
                tight = False
                X = X * 2
            else:
                X = X * 2
    ans = 0
    for a in A: ans += X ^ a
    
    print(ans)



if __name__ == "__main__":
    main()

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





x = 0
for i in range(k.bit_length()-1, -1, -1):
    cnt = 0
    for j in range(n):
        if a[j] >> i & 1 == 1:
            cnt += 1
    if cnt < (n + 1) // 2:
        t = x + (1 << i)
        if t <= k:
            x = t
ans = 0
for ai in a:
    ans += ai ^ x
print(ans)

Solution (Python):
def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    digit = len(str(bin(K)))-2
    digits1 = [0]*digit
    ans = 0
    for a in A:
        ans += a-a%(1<<digit)
        for i in range(digit):
            if a&1<<i:
                digits1[i] += 1
    x = 0
    for i in range(digit-1,-1,-1):
        if digits1[i]<N/2 and x+(1<<i) <=K:
            x += 1<<i
            ans += (1<<i)*(N-digits1[i])
        else:
            ans += (1<<i)*digits1[i]
    return ans
print(solve())

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

less = -float('inf')
eq = 0

for d in range(60)[::-1]:
    mask = (1 << d)

    one = len([0 for a in A if (a & mask) != 0])
    zero = N - one

    l = less + mask * max(one, zero)

    if (K & mask) != 0:
        l = max(l, eq + mask * one)

    less = l
    eq += mask * (one if (K & mask == 0) else zero)

print(max(less, eq))

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


d = format(K,'b')
dp = [[-1 for _ in range(2)] for _ in range(len(d) +1)]
dp[0][0] = 0
for i in range(len(d))[::-1]:
    if K == 0: break
    index = len(d) - i - 1
    cnt = 0
    for x in L:
        if x & (1 << i):
            cnt += 1
    
    tmp = 2 ** i 
    if dp[index][1] != -1:
        dp[index+1][1] =max(dp[index+1][1], dp[index][1] + max(cnt,N-cnt) * tmp)
    
    if d[index] == '1':
        
        if dp[index][0] != -1:
            dp[index+1][1] = max(dp[index+1][1],dp[index][0] + cnt * tmp)
        
        if dp[index][0] != -1:
            dp[index+1][0] = max(dp[index+1][0],dp[index][0] + (N-cnt)*tmp)
    else:
        
        if dp[index][0] != -1:
            dp[index+1][0] = max(dp[index+1][0],dp[index][0] + cnt*tmp)
ans = 0
for i in range(len(d),50):
    tmp = 2 ** i
    cnt = 0
    for x in L:
        if x & (1 << i):
            cnt += 1
    ans += cnt * tmp
print(ans + max(dp[len(d)][0],dp[len(d)][1],0))

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


d = format(K,'b')
dp = [[-1 for _ in range(2)] for _ in range(len(d) +1)]
dp[0][0] = 0
for i in range(len(d))[::-1]:
    if K == 0: break
    index = len(d) - i - 1
    cnt = 0
    for x in L:
        if x & (1 << i):
            cnt += 1
    
    tmp = 2 ** i 
    if dp[index][1] != -1:
        dp[index+1][1] =max(dp[index+1][1], dp[index][1] + max(cnt,N-cnt) * tmp)
    
    if d[index] == '1':
        
        if dp[index][0] != -1:
            dp[index+1][1] = max(dp[index+1][1],dp[index][0] + cnt * tmp)
        
        if dp[index][0] != -1:
            dp[index+1][0] = max(dp[index+1][0],dp[index][0] + (N-cnt)*tmp)
    else:
        
        if dp[index][0] != -1:
            dp[index+1][0] = max(dp[index+1][0],dp[index][0] + cnt*tmp)
ans = 0
for i in range(len(d),50):
    tmp = 2 ** i
    cnt = 0
    for x in L:
        if x & (1 << i):
            cnt += 1
    ans += cnt * tmp
print(ans + max(dp[len(d)][0],dp[len(d)][1],0))

Solution (Python):


def submit():
    n, k = (int(e) for e in input().split())
    a = [int(e) for e in input().split()]
    max_bit = 40
    bit_cnt = []
    
    b = 0
    bit = 1
    while b <= max_bit:
        cnt = sum(e & bit > 0 for e in a)
        bit_cnt.append(cnt)
        bit <<= 1
        b += 1

    isless = False
    curr_bit = 1 << max_bit
    ans = 0
    for i in range(max_bit + 1):
        
        k_bit = k & curr_bit > 0
        if not isless and k_bit == 0:
            
            
            ans += bit_cnt[max_bit - i] * curr_bit
        elif not isless and k_bit == 1:
            
            cnt1 = bit_cnt[max_bit - i]
            cnt0 = n - cnt1
            if cnt1 > cnt0:
                
                
                ans += cnt1 * curr_bit
                isless = True
            else:
                
                ans += cnt0 * curr_bit
        else:
            
            cnt1 = bit_cnt[max_bit - i]
            cnt0 = n - cnt1
            if cnt1 > cnt0:
                
                ans += cnt1 * curr_bit
            else:
                
                ans += cnt0 * curr_bit
        curr_bit >>= 1

    print(ans)


submit()

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

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


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

    d = defaultdict(int)
    for a in A:
        if a == 0:
            continue
        digit = int(math.log2(a))
        for i in range(digit + 1):
            if 1 << i & a:
                d[i] += 1

    x = 0
    if K != 0:
        digit = int(math.log2(K))
        for i in range(digit + 1)[::-1]:
            if N / 2 <= d[i]:
                continue
            else:
                if K < x + 2 ** i:
                    continue
                else:
                    x += 2 ** i

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

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys


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


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = K
    k = 1
    while K > 1:
        K //= 2
        k += 1
    if K == 0:
        print(sum(A))
        return
    cnt = [0 for _ in range(k)]
    for a in A:
        for i in range(k):
            if (a >> i) & 1:
                cnt[i] += 1
    X = 0
    if N % 2 == 0:
        n = N // 2 - 1
    else:
        n = N // 2
    for i in range(k):
        if cnt[k - i - 1] <= n:
            if X + (2 ** (k - i - 1)) <= B:
                X += 2 ** (k - i - 1)
    answer = 0
    for a in A:
        answer += X ^ a
    print(answer)


if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np
n, k = map(int,input().split())
a = np.array(input().split(),dtype=int)
n1 = [0 for i in range(40)]
g0 = [0 for i in range(40)]
g1 = [0 for i in range(40)]
ss = [0 for i in range(40)]
t2 = [1 for i in range(40)]

for i in range(40):
    n1[i] = np.count_nonzero(a&1)
    a >>= 1
    if i > 0:
        t2[i] = t2[i-1]*2
    g0[i] = n1[i]*t2[i]
    g1[i] = (n-n1[i])*t2[i]
    if n1[i] < n-n1[i]:
        ss[i] = ss[i-1]+g1[i]
    else:
        ss[i] = ss[i-1]+g0[i]

def DFS(ni,ki,sm):
    if ni == 0:
        if ki == 0:
            return sm+g0[0]
        else:
            return sm+ss[0]
    else:
        if ki//t2[ni] == 0:
            return DFS(ni-1,ki,sm+g0[ni])
        elif ki//t2[ni] > 1:
            return sm+ss[ni]
        else:
            return max(sm+g0[ni]+ss[ni-1],DFS(ni-1,ki-t2[ni],sm+g1[ni]))

ma = DFS(39,k,0)
print(ma)

Solution (Python):
import numpy as np
n, k = map(int,input().split())
a = np.array(input().split(),dtype=int)
n1 = [0 for i in range(40)]
g0 = [0 for i in range(40)]
g1 = [0 for i in range(40)]
ss = [0 for i in range(40)]
t2 = [1 for i in range(40)]

for i in range(40):
    n1[i] = np.count_nonzero(a&1)
    a >>= 1
    if i > 0:
        t2[i] = t2[i-1]*2
    g0[i] = n1[i]*t2[i]
    if n1[i] < n-n1[i]:
        g1[i] = (n-n1[i])*t2[i]
        ss[i] = ss[i-1]+g1[i]
    else:
        ss[i] = ss[i-1]+g0[i]


def DFS(ni,ki,sm):
    if ni == 0:
        if ki == 0:
            return sm+g0[0]
        else:
            return sm+ss[0]
    else:
        if g1[ni] == 0 or ki//t2[ni] == 0:
            return DFS(ni-1,ki,sm+g0[ni])
        elif ki//t2[ni] > 1:
            return sm+ss[ni]
        else:
            return max(sm+ss[ni-1],DFS(ni-1,ki-t2[ni],sm+g1[ni]))

ma = DFS(39,k,0)
print(ma)

Solution (Python):


import sys
readline = sys.stdin.readline

N, K = map(int, readline().split())
A = list(int(x) for x in readline().split())


bits = [0] * 50
for i in range(N):
    for j in range(50):
        if A[i]>>j&1:
            bits[j] += 1





dp = [[0] * 2 for _ in range(50)]

for i in range(49)[::-1]:
    
    check_bit = 1<<i
    
    if K&check_bit:
        
        
        dp[i][1] = dp[i+1][0] + (bits[i] * check_bit)
        
        if dp[i+1][1] != 0:
            dp[i][1] = max(dp[i][1], dp[i+1][1] + (max(N - bits[i], bits[i]) * check_bit))
        
        
        dp[i][0] = dp[i+1][0] + ((N - bits[i]) * check_bit)
    
    else:
        
        
        if dp[i+1][1] != 0:
            dp[i][1] = dp[i+1][1] + (max(N - bits[i], bits[i]) * check_bit)
        
        dp[i][0] = dp[i+1][0] + (bits[i] * check_bit)

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

Solution (Python):


import sys
readline = sys.stdin.readline

N, K = map(int, readline().split())
A = list(int(x) for x in readline().split())

bits = [0] * 50
for i in range(N):
    for j in range(50):
        if A[i]>>j&1:
            bits[j] += 1




ans = 0
tmp_K = 0
tmp_greed = 0
for i in range(50)[::-1]:
    if K>>i&1:
        tmp_greed = bits[i] * 1<<i
        for j in range(i)[::-1]:
            tmp_greed += max(bits[j], N-bits[j]) * 1<<j
        ans = max(tmp_greed + tmp_K, ans)
        tmp_K += (N-bits[i]) * 1<<i
    else:
        tmp_K += bits[i] * 1<<i

ans = max(ans, tmp_K)
print(ans)