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 sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



N, K = MAP()
A = LIST()

n = max(A+[K]).bit_length()
cnt = [[0, 0] for _ in range(n)]

for a in A:
	b = "{:b}".format(a).zfill(n)[::-1]
	for i in range(n):
		cnt[i][int(b[i])] += 1

max_X = []
for cnt_0, cnt_1 in cnt:
	if cnt_0 <= cnt_1:
		max_X.append(0)
	else:
		max_X.append(1)
max_X = max_X[::-1]     

k = "{:b}".format(K).zfill(n)

if len(k) == n:
	for i in range(n):
		if int(k[i]) > max_X[i]:
			break
		elif int(k[i]) < max_X[i]:
			max_X[i] = 0

X = 0
for i, p in enumerate(max_X[::-1]):
	X += 2**i*p


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

print(ans)

Solution (Python):


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

    ans = 0
    for d in range(40,-2,-1):
        
        if d != -1 and not (K & (1<<d)):
            continue

        tmp = 0
        for e in range(40,-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)
        ans = max(ans,tmp)

    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
n , k = map(int,input().split())
a = list(map(int,input().split()))
bi = [0 for i in range(41)]
if n % 2 == 0:
    kahan = n//2-1
elif n % 2 == 1:
    kahan = n//2
for i in range(n):
    for j in range(41):
        bi[j] += (a[i] >> j) & 1

for i in reversed(range(41)):
    if k < pow(2,i):
        continue
    elif k >= pow(2,i):
        if bi[i] <= kahan:
            bi[i] = n - bi[i]
            k -= pow(2,i)
ans = 0
for i in range(41):
    ans += bi[i]*pow(2,i)

print(ans)

Solution (Python):
import sys
import itertools

import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines



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

dp = [[-1] * 2 for _ in range(51)]


dp[50][0] = 0
for i in range(49, -1, -1):
    cnt = 0
    for a in A:
        cnt += a >> i & 1
    val0 = cnt << i
    val1 = (N - cnt) << i

    if dp[i + 1][1] >= 0:
        dp[i][1] = max(dp[i][1], dp[i + 1][1] + max(val0, val1))
    if dp[i + 1][0] >= 0:
        if K >> i & 1 > 0:
            dp[i][0] = max(dp[i][0], dp[i + 1][0] + val1)
            dp[i][1] = max(dp[i][1], dp[i + 1][0] + val0)
        else:
            dp[i][0] = max(dp[i][0], dp[i + 1][0] + val0)
print(max(dp[0][0], dp[0][1]))

Solution (Python):
import sys
import itertools

import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines



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

def rec(i, is_same):
    res = 0
    x, y = 0, 0
    for a in A:
        x += 0 ^ (a >> i & 1)
        y += 1 ^ (a >> i & 1)
    if K >> i & 1 == 0 and is_same:
        res = rec(i - 1, is_same) + x
    else:
        res = max(rec(i - 1, False) + x, rec(i - 1, True) + y)
    return res

def f(n):
    res = 0
    while n > 0:
        res += 1
        n //= 2
    return res

dp = [[-1 for _ in range(2)] for _ in range(50)]
d = 48
dp[d + 1][0] = 0
for i in range(d, -1, -1):
    x, y = 0, 0
    for a in A:
        x += 0 ^ (a >> i & 1)
        y += 1 ^ (a >> i & 1)
    x <<= i
    y <<= i

    if dp[i + 1][1] >= 0:
        dp[i][1] = max(dp[i][1], dp[i + 1][1] + max(x, y))
    if dp[i + 1][0] >= 0:
        if K >> i & 1 == 0:
            dp[i][0] = max(dp[i][0], dp[i + 1][0] + x)
        else:
            dp[i][1] = max(dp[i][1], dp[i + 1][0] + x)
            dp[i][0] = max(dp[i][0], dp[i + 1][0] + y)
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
print(max(dp[0][0], dp[0][1]))

Solution (Python):
import math
import collections
import itertools
import heapq
import bisect
import sys


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

    c = [0] * 40
    res = 0
    for a in A:
        for bit in range(40):
            if a & (1<<bit):
                c[bit] += 1

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

    for a in A:
        res += x^a

    print(res)
  

if __name__ == "__main__":
    main()

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):
import numpy as np

def binstr(n):
    return np.array(list(map(int,list(bin(n)[2:].rjust(40,'0')))))

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

AA = sum([binstr(i) for i in A])
X = 0
ans = 0
for i in range(40):
    if AA[i] > N-AA[i]:   
        ans += AA[i]*(2**(39-i))
    else:                 
        if X+2**(39-i) <= K:    
            ans += (N-AA[i])*(2**(39-i))
            X += 2**(39-i)
        else:                  
            ans += AA[i]*(2**(39-i))

print(ans)

Solution (Python):
import numpy as np

def binstr(n):
    return np.array(list(map(int,list(bin(n)[2:].rjust(40,'0')))))

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

AA = sum([binstr(i) for i in A])
X = 0
ans = 0
for i in range(40):
    if AA[i] > N-AA[i]:   
        ans += AA[i]*(2**(39-i))
    else:                 
        if X+2**(39-i) <= K:    
            ans += (N-AA[i])*(2**(39-i))
            X += 2**(39-i)
        else:                  
            ans += AA[i]*(2**(39-i))

print(ans)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
bin_str1 = format(K+1, "b")
bin_str2 = format(max(A), "b")
l = max(len(bin_str1), len(bin_str2))
P = [0]*l

for i in range(N):
    t = format(A[i], "b")
    t = t[::-1]
    for j in range(len(t)):
        if t[j] == "1":
            P[j] += 1

if N % 2 == 0:
    bor = N//2
else:
    bor = N//2 + 1

result = 0
bin_str1 = bin_str1[::-1]
for i in range(len(bin_str1)):
    s = 1
    ans = 0
    if bin_str1[i] == "1":
        for j in range(i):
            if P[j] >= bor:
                ans += s*P[j]
            else:
                ans += s*(N - P[j])
            s *= 2
        ans += s*P[i]
        s *= 2
        for j in range(i+1, len(bin_str1)):
            if bin_str1[j] == "0":
                ans += s*P[j]
            else:
                ans += s*(N - P[j])
            s *= 2
        if len(bin_str2) > len(bin_str1):
            for j in range(len(bin_str1), len(bin_str2)):
                ans += s*P[j]
                s *= 2
    result = max(ans, result)

print(result)

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
digits = [0]*40
for i in a:
    for j in range(40):
        digits[j] += i>>j&1
ans = 0
flg = True
for i in range(39, -1, -1):
    if flg and k>>i&1==0:
        ans += digits[i]*2**i
        continue
    ans += max(digits[i], n-digits[i])*2**i
    if flg and digits[i]>=(n+1)//2:
        flg = False
print(ans)

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
X=1<<50
Y,Z=0,0
M=0
for i in range(50):
  X>>=1
  Y,Z=0,0
  for j in range(N):
    if X&A[j]:
      Y+=1
    else:
      Z+=1
  if Y<Z and M+X<=K:
    M+=X
P=0
for i in range(N):
  P+=M^A[i]
print(P)

Solution (Python):
import collections
import math
n,k = map(int, raw_input().split(' '))
ais = map(int, raw_input().split(' '))
r = 0
m = 42
x = 0
for ii in range(m, -1, -1):
	cc = collections.Counter([(ai >> ii) & 1 for ai in ais])
	if (x + (1 << ii) <= k):
		if cc[0] > cc[1]: x += (1 << ii)
		
	  
for ai in ais:
	r += ai ^ x
print r

Solution (Python):

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

max_a = max(max(A_list), K)
max_len = 0
tmp = max_a
while tmp > 0:
    max_len += 1
    tmp//=2

K_bits = [1 if (K >> j &1) else 0 for j in range(max_len)][::-1]

sum_1_bits = [0] * max_len
for a in A_list:
    a_bits = [j for j in range(max_len) if (a >> j &1)]
    for bit in a_bits:
        sum_1_bits[bit] += 1
sum_1_bits = sum_1_bits[::-1]



dp = [[0] * max_len for i in range(2)]
border = N/2
twice = 2 ** (max_len-1)
highest_digit = 0
i = 0

if K == 0:
    res = 0
    for b in sum_1_bits:
        res += twice * b
        twice //= 2

    print(res)
    exit()
    
while True:
    if K_bits[i] == 1:
        highest_digit = i
        break
    dp[0][i] = dp[0][i-1] + twice * sum_1_bits[i]
    dp[1][i] = dp[1][i-1] + twice * sum_1_bits[i]
    twice //= 2
    i += 1

dp[0][highest_digit] = dp[0][highest_digit-1] + twice * (N-sum_1_bits[highest_digit])
dp[1][highest_digit] = dp[1][highest_digit-1] + twice * sum_1_bits[highest_digit]
twice //= 2

for i in range(highest_digit+1, max_len):

    ibits = sum_1_bits[i]
    dp[1][i] = dp[1][i-1] + twice * max(ibits, N-ibits)
    if K_bits[i] == 1:
        dp[1][i] = max(dp[1][i], dp[0][i-1] + twice * ibits)
    k_side = ibits if K_bits[i] == 0 else N-ibits
    dp[0][i] = dp[0][i-1] + twice * k_side
    twice //= 2

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

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, k = map(int, readline().split())
    a = list(map(int, readline().split()))
    zero_plus = [0] * 60  
    one_plus = [0] * 60

    for x in a:
        s = format(x, "b")
        s = s[::-1]
        l = len(s)
        for i in range(60):
            if i >= l:
                one_plus[i] += 1
            elif s[i] == "0":
                one_plus[i] += 1
            else:
                zero_plus[i] += 1

    dp = dict()
    dp[True] = [-INF] * 61
    dp[False] = [0] * 61

    k_bin = format(k, "b")
    k_bin_length = k.bit_length()

    for i in range(59, -1, -1):
        cur = 2 ** i
        d = k_bin_length - i - 1
        if d < 0:
            dp[False][i] = dp[False][i + 1] + zero_plus[i] * cur
        else:
            zero = cur * zero_plus[i]
            one = cur * one_plus[i]
            if k_bin[d] == "1":
                dp[True][i] = max(dp[False][i + 1] + zero, dp[True][i + 1] + one, dp[True][i + 1] + zero)
                dp[False][i] = dp[False][i + 1] + one
            else:
                dp[True][i] = max(dp[True][i + 1] + zero, dp[True][i + 1] + one)
                dp[False][i] = dp[False][i + 1] + zero

    print(max(dp[True][0], dp[False][0]))


if __name__ == '__main__':
    main()

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
d={j:0 for j in range(41)}
for ai in a:
  for j in range(41):
    if (ai>>j) & 1:
      d[j]+=1
ans=0
l=len(bin(k))-3
import sys
sys.setrecursionlimit(10**7)

def dp(m,t): 
  if m<0:return 0
  ret=0
  if t==1: 
    for i in range(m+1):
      tmp=max(0,n-2*d[i])
      ret+=pow(2,i)*tmp
  else:
    if (k>>m)&1: 
      
      tmp1=dp(m-1,0)+(n-2*d[m])*pow(2,m)
      
      tmp0=dp(m-1,1)                    
      ret+=max(tmp1,tmp0)
    else:
      ret+=dp(m-1,0)
  return ret

print(sum(a)+dp(l,0))

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,k = inpl()
a = inpl()
a.sort()
ln = len(bin(max(k,a[-1]))) - 2 
bit = [0 for i in range(ln)]
res = 0
ans = 0
for x in a:
    for i in range(ln):
        if i: 
            (x>>1) % 2
            x = x>>1
        if x%2:
            bit[i] += 1
    
for i,j in enumerate(bit):
    if j < n/2:
        bit[i] = 1
    else:
        bit[i] = 0

for i in range(ln):
    if bit[ln-i-1]:
        c = pow(2,ln-i-1)
        if k >= c:
            res += c
            k -= c

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

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,k = inpl()
a = inpl()
ln = max(len(bin(max(a))), len(bin(k))) - 2
c = [0] * ln
res = 0
for x in a:
    for i in range(ln):
        c[i] += (x>>i)%2

for i in range(ln)[::-1]:
    if c[i] < (n+1)//2:
        
        now = pow(2,i)
        if res + now <= k:
            res += now
ans = 0
for x in a:
    ans += res^x
print(ans)

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

B = [[0]*2 for _ in range(42)]
for a in A:
    b = format(a, 'b')
    b = list(b)
    b.reverse()
    for i in range(len(b)):
        if b[i] == '1':
            B[i][1] += 1

for i in range(42):
    if B[i][1] != 0:
        B[i][0] = n-B[i][1]
B.reverse()

temp = 0
max_ = 0
for i, (b0, b1) in enumerate(B):
    if b1 == 0:
        if temp + 2**(41-i) <= k:
            max_ += n*2**(41-i)
            temp += 2**(41-i)
    else:
        if b0 >= b1:
            if temp + 2**(41-i) <= k:
                max_ += b0*2**(41-i)
                temp += 2**(41-i)
            else:
                max_ += b1*2**(41-i)
                temp += 0
        else:
            max_ += b1*2**(41-i)
            temp += 0
print(max_)

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

B = [[0]*2 for _ in range(42)]
for a in A:
    b = format(a, 'b')
    b = list(b)
    b.reverse()
    for i in range(len(b)):
        if b[i] == '1':
            B[i][1] += 1

for i in range(42):
    if B[i][1] != 0:
        B[i][0] = n-B[i][1]
B.reverse()

temp = 0
max_ = 0
for i, (b0, b1) in enumerate(B):
    if b1 == 0:
        if temp + 2**(41-i) <= k:
            max_ += n*2**(41-i)
            temp += 2**(41-i)
    else:
        if b0 >= b1:
            if temp + 2**(41-i) <= k:
                max_ += b0*2**(41-i)
                temp += 2**(41-i)
            else:
                max_ += b1*2**(41-i)
                temp += 0
        else:
            max_ += b1*2**(41-i)
            temp += 0
print(max_)

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
scores0=[0]*50
scores1=[0]*50
for i in range(n):
  s='{0:b}'.format(a[i])
  s2=[]
  for j in range(len(s)):
    s2.append(s[j])
  s2.reverse()
  for j in range(50-len(s)):
    s2.append('0')
  for j in range(50):
    if s2[j]=='0':
      scores0[j]+=1
    else:
      scores1[j]+=1
k2=[]
k='{0:b}'.format(k)
for j in range(len(k)):
  k2.append(k[j])
k2.reverse()
for j in range(50-len(k)):
  k2.append('0')
maxscore=0
for start in range(-1,50):
  if start>=0 and k2[start]=='0':
    continue
  score=0
  for j in range(49,start,-1):
    if k2[j]=='1':
      score+=scores0[j]*pow(2,j)
    else:
      score+=scores1[j]*pow(2,j)
  if start==-1:
    maxscore=max(maxscore,score)
    continue
  score+=scores1[start]*pow(2,start)
  for j in range(start-1,-1,-1):
    score+=max(scores0[j],scores1[j])*pow(2,j)
  maxscore=max(maxscore,score)
print(maxscore)

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

st = lambda n: bin(n)[2:]
n,k = map(int,readline().split())
a = np.array([int(i) for i in readline().split()])

INF = 10**12
mm = INF.bit_length()
chk = [((a >> k) & 1).sum() for k in range(mm)]

ll = []
q = 0
for num,cc in enumerate(chk):
  if cc < n/2:
    q += 2**(num)
  ll.append((num,2**num*(n-cc),2**num*cc))
    
max_V = 0
KK = (k+1).bit_length()
sk = st(k+1).zfill(mm)
sq = st(q).zfill(mm)

for i in range(KK):
  if (k+1)>>i&1 == 1:
    op = q
    if q>>i&1 == 1:
      op -= 2**i
    I = KK-i
    for j in range(mm-KK+I):
      if sq[j] == '1' and sk[j] == '0':
        op -= 2**(mm-1-j)
    V = 0
    for nm,v_1,v_0 in ll:
      if op>>nm & 1 == 1:     
        V += v_1
      else:
        V += v_0
    max_V = max(max_V, V)
    
print(max_V)

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

st = lambda n: bin(n)[2:]
n,k = map(int,readline().split())
a = [int(i) for i in readline().split()]

INF = 10**12
mm = INF.bit_length()
chk = np.array([list(st(i).zfill(mm)) for i in a])

ll = []
q = 0
for num,i in enumerate(chk.T):
  cc = np.count_nonzero(i == '1')
  if cc < n/2:
    q += 2**(mm-1-num)
  ll.append((mm-1-num,2**(mm-1-num)*(n-cc),2**(mm-1-num)*cc))
    
max_V = 0
KK = (k+1).bit_length()
sk = st(k+1).zfill(mm)
sq = st(q).zfill(mm)

for i in range(KK):
  if (k+1)>>i&1 == 1:
    op = q
    if q>>i&1 == 1:
      op -= 2**i
    I = KK-i
    for j in range(mm-KK+I):
      if sq[j] == '1' and sk[j] == '0':
        op -= 2**(mm-1-j)
    V = 0
    for nm,v_1,v_0 in ll:
      if op>>nm & 1 == 1:     
        V += v_1
      else:
        V += v_0
    max_V = max(max_V, V)
    
print(max_V)

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





N,K = IL()
A = IL()

data = [0 for i in range(50)]
for i in range(50):
  for a in A:
    if (a>>i) & 1:
      data[i] += 1

now = 0
for i in range(50)[::-1]:
  if now + (1<<i) > K: continue
  if data[i] < N/2: now += (1<<i) 
ans = 0
for i in range(50):
  ans += (N-data[i] if (now>>i) & 1 else data[i]) * (1<<i)
print(ans)

Solution (Python):


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n,k=MI()
lis=LI()
u=max(max(lis),k)
memo=0
for i in range(45):
    x=(u>>i)%2
    if x==1:
        memo=i
memo+=1

table=[0 for i in range(memo)]
for i in range(n):
    for j in range(memo):
        x=(lis[i]>>j)%2
        if x==1:
            table[j]+=1

table2=[[0,0] for i in range(memo)]
for i in range(memo):
    table2[i][0]=abs(n-2*table[i])*2**i
    table2[i][1]=i+1
    if n-2*table[i]<0:
        table2[i][1]*=(-1)

table2.sort(reverse=True)


maxx=0
ans_table=[0 for i in range(memo)]
for i in range(memo):
    if table2[i][1]>0:
        maxx+=2**(table2[i][1]-1)
        if maxx<=k:
            ans_table[table2[i][1]-1]=1
        else:
            ans_table[table2[i][1]-1]=0
            maxx-=2**(table2[i][1]-1)
    else:
        ans_table[abs(table2[i][1])-1]=0

ans=0
for i in range(memo):
    if ans_table[i]==1:
        ans+=(2**i)*(n-table[i])
    else:
        ans+=(2**i)*table[i]
print(ans)

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

dp=[[-1]*2 for i in range(51)]
dp[50][0]=0

for i in reversed(range(50)):
    mask=1<<i
    bit1=0
    bit0=0
    for a in A:
        if a&mask:
            bit1+=1
        else:
            bit0+=1
    p1=bit0*mask
    p0=bit1*mask
    if dp[i+1][1]!=-1:
        dp[i][1]=dp[i+1][1]+max(p1,p0)
    if K&mask:
        dp[i][0]=dp[i+1][0]+p1
        dp[i][1]=max(dp[i][1],dp[i+1][0]+p0)
    else:
        dp[i][0]=dp[i+1][0]+p0
print(max(dp[0]))

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
s=sum(A)
dp=[[-1]*2 for i in range(42)]
dp[0][0]=0
bit=[0]*41
for i in range(41):
    mask=1<<(40-i)
    cnt0,cnt1=0,0
    for j in range(N):
        if A[j]&mask:
            cnt1+=1
        else:
            cnt0+=1
    cost0,cost1=cnt1*mask,cnt0*mask
    if dp[i][1]!=-1:
        dp[i+1][1]=max(dp[i+1][1],dp[i][1]+max(cost0,cost1))
    if K&mask:
        dp[i+1][1]=max(dp[i+1][1],dp[i][0]+cost0)
        dp[i+1][0]=max(dp[i+1][0],dp[i][0]+cost1)
    else:
        dp[i+1][0]=dp[i][0]+cost0
print(max(dp[-1]))

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul
from pprint import pprint
import numpy as np


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, k = LI()
A = np.array(LI(), dtype=np.int64)
bit_cnt = [((A >> k) & 1).sum() for k in range(40)]
ans = 0
for i in range(40):
    if k >> i & 1 == 0:
        continue
    ret = 0
    ret += bit_cnt[i] * (1 << i)
    for j in range(i + 1, 40):
        if k >> j & 1:
            ret += (n -  bit_cnt[j]) * (1 << j)
        else:
            ret += bit_cnt[j] * (1 << j)
    for l in range(i):
        ret += max(n - bit_cnt[l], bit_cnt[l]) * (1 << l)
    ans = max(ans, ret)


ret = 0
for a in A:
    ret += k ^ a

print(max(ret, ans))

Solution (Python):


import math



from collections import deque
from collections import Counter




n,k=map(int,input().split())
a=list(map(int,input().split()))
x=k.bit_length()
res=0
for i in range(x):
  c1=0
  c0=0
  for j in range(n):
    if (a[j]>>i & 1)==1:
      c1+=1
    else:
      c0+=1
  if c0>c1:
    res+=2**i
ans=0
if res>k:
  for i in range(x):
    k_res=(k>>(x-i-1))&1
    r=res>>(x-i-1)&1
    if k_res==0 and r==1:
      res-=2**(x-i-1)
    if res<=k:
      break
      
for i in range(n):
  ans+=res^a[i]
print(ans)

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
dp=[0]*41
bp=[0]*41
for i in range(N):
  o=len(bin(A[i]))
  for j in range(o-2):
    if (A[i]>>j)&1==1:
      dp[j]+=1
ans=0
count=0
for i in range(len(dp)-1,-1,-1):
  bp[i]=N-dp[i]
  if dp[i]<bp[i] and count+pow(2,i)<=K:
    count+=pow(2,i)
ans=0
for i in range(N):
  ans+=(count^A[i])
print(ans)

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
bounded = True
for i in range(40, -1, -1):
    d = 1 << i
    cnt1 = sum(d & ai > 0 for ai in a)
    cnt0 = n - cnt1
    if bounded and k & d == 0 or cnt1 >= cnt0:
        ans += cnt1 * d
        if k & d > 0:
            bounded = False
    else:
        ans += cnt0 * d
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 c>=n-c or k<t: ans += t*c
    else: ans += t*(n-c);k-=t
    t = t>>1
print(ans)

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


def read():
    N, K = map(int, input().strip().split())
    A = list(map(int, input().strip().split()))
    return N, K, A


def solve(N, K, A):
    L = max(K, max(A), 1).bit_length()
    k = [0 for i in range(L)]
    i = 0
    while K:
        k[i] += K & 1
        i += 1
        K >>= 1
    b = [0 for i in range(L)]
    for a in A:
        i = 0
        x = a
        while x:
            b[i] += x & 1
            i += 1
            x >>= 1
    k = k[::-1]
    b = b[::-1]
    
    
    dp = [[0, 0] for i in range(L+1)]
    nonzero = False
    for i in range(L):
        if k[i] == 1:
            dp[i+1][1] = (dp[i][1] << 1) + (N-b[i])
            if nonzero:
                dp[i+1][0] = max((dp[i][1] << 1) + b[i], (dp[i][0] << 1) + max(b[i], N-b[i]))
            else:
                dp[i+1][0] = (dp[i][1] << 1) + b[i]
            nonzero = True
        else:
            dp[i+1][1] = (dp[i][1] << 1) + b[i]
            dp[i+1][0] = (dp[i][0] << 1) + max(b[i], N-b[i]) if nonzero else 0
    return max(dp[L][1], dp[L][0])


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

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


def read():
    N, K = map(int, input().strip().split())
    A = list(map(int, input().strip().split()))
    return N, K, A


def solve(N, K, A):
    L = max(K, max(A), 1).bit_length()
    k = [0 for i in range(L)]
    i = 0
    while K:
        k[i] += K & 1
        i += 1
        K >>= 1
    b = [0 for i in range(L)]
    for a in A:
        i = 0
        x = a
        while x:
            b[i] += x & 1
            i += 1
            x >>= 1
    k = k[::-1]
    b = b[::-1]
    
    
    dp = [[-1, -1] for i in range(L+1)]
    dp[0][1] = 0
    for i in range(L):
        if dp[i][0] >= 0:
            dp[i+1][0] = (dp[i][0] << 1) + max(b[i], N-b[i])
        
        if k[i] == 1:
            dp[i+1][0] = max(dp[i+1][0], (dp[i][1] << 1) + b[i])
            dp[i+1][1] = (dp[i][1] << 1) + (N-b[i])
        else:
            dp[i+1][1] = (dp[i][1] << 1) + (b[i])
    return max(dp[L][1], dp[L][0])


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))