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()))
Kb = format(K, 'b')
f = lambda x: sum(a ^ x for a in A)
table = [f(2 ** i) - f(0) for i in range(42)]
candy = {i: x for i, x in enumerate(table) if x > 0 and 2 ** i <= K}
mask = [K]
for i in range(len(Kb) - 1, -1, -1):
    if K & (1 << i):
        mask += [K ^ (1 << i) | ((1 << i) - 1)]
res = 0
for m in mask:
    tmp = 0
    for b in range(42):
        if m & (1 << b) and b in candy:
            tmp += candy[b]
    res = max(res, tmp)
print(res + f(0))

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
Kb = format(K, 'b')
f = lambda x: sum(a ^ x for a in A)
table = [f(2**i) - f(0) for i in range(42)]
candy = {i: x for i, x in enumerate(table) if x > 0 and 2 ** i <= K}
if candy:
    mask = [K]
    for i in range(len(Kb) - 1, -1, -1):
        if K & (1 << i):
            mask += [K ^ (1 << i) | ((1 << i) - 1)]
    res = 0
    for m in mask:
        tmp = 0
        for b in range(42):
            if m & (1 << b) and b in candy:
                tmp += candy[b]
        res = max(res, tmp)
    print(res + f(0))
else:
    print(f(0))

Solution (Python):
def Sum_xxor(ans_tmp,A,tmp,ind_max):

    ans_ret = 0
    ans_x = ans_tmp

    for i in range(ind_max):
        if Ones[i] <= N-Ones[i]:
            ans_x += bits[i]*1
        else:
            ans_x += bits[i]*0

    for a in A:
        ans_ret += ans_x ^ a

    return ans_ret

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

Ones   = [0 for _ in range(41)]
bits  = [0 for _ in range(41)]

for i in range(41):
    if i == 0:
        bit = 1
    else:
        bit *= 2
    bits[i] = bit

    Ones_i = 0

    for a in A:
        if a & bit:
            Ones_i += 1

    Ones[i] = Ones_i

t,ans = bit, 0
ind = 41
ans_tmp = 0
ch = 0
while t:
    if ch == 0:
        if not(t & (K+1)):
            ans_tmp += 0
        else:
            ch = 1

            ind_max = ind - 1
            ans = max(ans, Sum_xxor(ans_tmp,A,Ones,ind_max))

            ans_tmp += t

    else:
        if t & (K+1):

            ind_max = ind - 1
            ans = max(ans, Sum_xxor(ans_tmp,A,Ones,ind_max))

            ans_tmp += t


    t  //= 2
    ind -= 1


print(ans)

Solution (Python):
def Sum_xxor(ans_tmp,A,tmp,saiteki,ind_max):

    ans_ret = 0
    ans_x = ans_tmp

    for i in range(41):
        if i < ind_max:
            if tmp[i] <= N-tmp[i]:
                ans_x += bits[i]*1
            else:
                ans_x += bits[i]*0
    for a in A:
        ans_ret += ans_x ^ a

    return ans_ret

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

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

tmp   = [0 for _ in range(41)]
bits  = [0 for _ in range(41)]
saiteki = [0 for _ in range(41)]

for i in range(41):
    if i == 0:
        bit = 1
    else:
        bit *= 2
    bits[i] = bit

    tmp_i = 0

    for a in A:
        if a & bit:
            tmp_i += 1

    tmp[i] = tmp_i
    saiteki[i] = max(tmp_i,N-tmp_i)*bit

t,ans = bit, 0
ind = 41
ans_tmp = 0
ch = 0
while t:

    if ch == 0:
        if not(t & (K+1)):
            ans_tmp += 0
        else:
            ch = 1

            ind_max = ind - 1
            ans = max(ans, Sum_xxor(ans_tmp,A,tmp,saiteki,ind_max))

            ans_tmp += t

    else:
        if t & (K+1):

            ind_max = ind - 1
            ans = max(ans, Sum_xxor(ans_tmp,A,tmp,saiteki,ind_max))

            ans_tmp += t


    t  //= 2
    ind -= 1


print(ans)

Solution (Python):
from math import ceil
N,K = map(int,input().split())
A = list(map(int,input().split()))
ans = 0
l = len(bin(K))-2 if K!=0 else 0
for i in range(l)[::-1]:
    cnt = 0
    for a in A:
        tmp = (a>>i)&1
        if not tmp:
            cnt += 1
    if ceil(N/2)<=cnt and ans+(2**i)<=K:
        ans += (2**i) 

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

Solution (Python):
import math

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


lk=str(41)

B=[]
for i in range(n):
    B.append(format(A[i],str(lk.zfill(2))+"b"))



P=[]
ss=1
for i in range(41-1,-1,-1):
    po0=0
    po1=0
    for j in range(n):
        
        if B[j][i]=="1" :
            po0+=ss
        else :
            po1+=ss
    P.append([po0,po1])
    ss*=2



pmax=[]
for i in range(len(P)):
    pmax.append(max(P[i]))

k2=str(format(k,"b"))
k22=str(format(k,"041b"))


le=1
ri=1
ma=0
for i in range(1,len(k22)+1):
    ma+=P[i-1][int(k22[-i])]
ma1=ma



    
while ri<=len(k2) :
    if k2[-ri]=="0" :
        ri+=1
    else :
        ma2=ma1
        for i in range(le,ri):
            ma2-=P[i-1][0]
            ma2+=pmax[i-1]
        ma2-=P[ri-1][1]
        ma2+=P[ri-1][0]
        
        
        ma=max(ma,ma2)
        ma1=ma2
        le=ri
        ri+=1

print(ma)

Solution (Python):


def XXOR(N,K,A):
    
    
    ans = 0

    
    bit_stand = [len([1 for a in A if (a & 1<<b) != 0]) for b in range(40)]

    
    for i in range(39,-2,-1):

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

        tmp = 0
        for e in range(39,-1,-1): 
            bit_mask = 1<<e
            num = bit_stand[e]

            if e>i: 
                if (bit_mask & K) == 0: 
                    tmp += bit_mask * num
                else:                   
                    tmp += bit_mask * (N-num) 
            elif e==i: 
                tmp += bit_mask * num
            else: 
                tmp += bit_mask * max(num,N-num)
        
        ans = max(ans, tmp)
    
    return ans


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

Solution (Python):
N, K = map(int, input().split())
a = list(map(int, input().split()))
max_bit = 40
ans = 0
 
for bit in range(max_bit, -1, -1):
    num = 2**bit
    bit_count = len([1 for n in a if n&num > 0])
    if bit_count < N - bit_count and num <= K:
        bit_count = N - bit_count
        K -= num
    ans += num * bit_count
 
print(ans)

Solution (Python):
import numpy as np
n, k = map(int, input().split())
a = np.array(list(map(int, input().split())))
z = [(a&1<<i).sum() for i in range(40)]
o = [max((n<<i)-z[i], z[i])  for i in range(40)]
c = np.cumsum(o)
r = s = 0
for i in reversed(range(40)):
    if k&1<<i:
        if i > 0:
            r = max(r, s + z[i] + c[i-1])
        s += o[i]
    else:
        s += z[i]
print(max(r, s))

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,k = li()
a = list(li())

zer_rew = [0]*40
one_rew = [0]*40

for idx in range(39,-1,-1):
    bit = 1<<idx
    
    for ai in a:
        if ai & bit:
            zer_rew[39-idx] += bit
        else:
            one_rew[39-idx] += bit
            
INF = float('inf')
dp = [[-INF, 0] for _ in range(41)]
for digit in range(40):
    if k & (1<<(39-digit)):
        dp[digit+1][1] = dp[digit][1] + one_rew[digit]
        
        dp[digit+1][0] = max(dp[digit][1] + zer_rew[digit],
                             dp[digit][0] + zer_rew[digit],
                             dp[digit][0] + one_rew[digit])
        
    else:
        dp[digit+1][1] = dp[digit][1] + zer_rew[digit]
        
        dp[digit+1][0] = max(dp[digit][0] + zer_rew[digit],
                             dp[digit][0] + one_rew[digit])
        
print(max(dp[-1]))

Solution (Python):
B='{:041b}'.format
n,k,*a=map(int,open(0).read().split())
if not k:
  print(sum(a))
  exit()
l=[0]*41
for i in a:
  for j,t in enumerate(B(i)):
    if int(t):l[j]+=1
dp=[[0,-1]for i in range(41)]
for i,f in enumerate(map(int,B(k))):
  if not i:continue
  v0,v1=(n-l[i])*pow(2,40-i),l[i]*pow(2,40-i)
  if f:
    dp[i][0]=dp[i-1][0]+v0
    if dp[i-1][1]>=0:
      dp[i][1]=max(dp[i-1][0]+v1,dp[i-1][1]+max(v0,v1))
    else:
      dp[i][1]=dp[i-1][0]+v1
  else:
    dp[i][0]=dp[i-1][0]+v1
    if dp[i-1][1]>=0:
      dp[i][1]=dp[i-1][1]+max(v0,v1)
print(max(dp[-1]))

Solution (Python):
B='{:041b}'.format
n,k,*a=map(int,open(0).read().split())
if not k:
  print(sum(a))
  exit()
l=[0]*41
for i in a:
  for j,t in enumerate(B(i)):
    if int(t):l[j]+=1
dp=[[0,-1]for i in range(41)]
for i,f in enumerate(map(int,B(k))):
  if not i:continue
  v0,v1=(n-l[i])*pow(2,40-i),l[i]*pow(2,40-i)
  if f:
    dp[i][0]=dp[i-1][0]+v0
    if dp[i-1][1]>=0:
      dp[i][1]=max(dp[i-1][0]+v1,dp[i-1][1]+max(v0,v1))
    else:
      dp[i][1]=dp[i-1][0]+v1
  else:
    dp[i][0]=dp[i-1][0]+v1
    if dp[i-1][1]>=0:
      dp[i][1]=dp[i-1][1]+max(v0,v1)
print(max(dp[-1]))

Solution (Python):
N,K = map(int,input().split())
Ni = list(map(int,input().split()))
    
K_bit = format(K, 'b')
max_K = 0
max_bit = len(K_bit)

cnt_bit = 1 << (max_bit-1)

for i in range(max_bit):
    cnt = 0
    for j in Ni:
        if j & cnt_bit:
            cnt += 1
            
    if cnt*2 <= N and (max_K + cnt_bit) <= K: 
        max_K += cnt_bit
        
    cnt_bit >>= 1
    
ans = sum([max_K ^ j for j in Ni])
        
print(ans)

Solution (Python):
MAX_DIGIT = 40

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

digit = [1 << i for i in range(MAX_DIGIT)]

sum_d = [[0] * 2 for _ in range(MAX_DIGIT)]
for ai in an:
    for i in range(MAX_DIGIT):
        d = (ai >> i) & 1
        sum_d[i][d] += digit[i]

sum_max = [0] * MAX_DIGIT
sum_max[0] = max(sum_d[0])
for i in range(MAX_DIGIT - 1):
    sum_max[i + 1] = sum_max[i] + max(sum_d[i + 1])

dp = [-1] * MAX_DIGIT
dp[0] = sum_d[0][0 if (k & 1) == 1 else 1]
for i in range(MAX_DIGIT - 1):
    d = k >> (i + 1) & 1
    if d == 0:    
        dp[i + 1] = sum_d[i + 1][1] + dp[i]
    if d == 1:    
        dp[i + 1] = max(sum_d[i + 1][0] + dp[i], sum_d[i + 1][1] + sum_max[i])
print(dp[-1])

Solution (Python):





MAX_DIGIT = 40

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

digit = [1 << i for i in range(MAX_DIGIT)]

sum_d = [[0] * 2 for _ in range(MAX_DIGIT)]
for ai in an:
    for i in range(MAX_DIGIT):
        d = (ai >> i) & 1
        sum_d[i][d] += digit[i]


sum_max = [0] * MAX_DIGIT
sum_max[0] = max(sum_d[0])
for i in range(MAX_DIGIT - 1):
    sum_max[i + 1] = sum_max[i] + max(sum_d[i + 1])


dp = [-1] * MAX_DIGIT

dp[0] = sum_d[0][0 if (k & 1) == 1 else 1]
for i in range(MAX_DIGIT - 1):
    d = k >> (i + 1) & 1
    if d == 0:    
        dp[i + 1] = sum_d[i + 1][1] + dp[i]
    if d == 1:    
        dp[i + 1] = max(sum_d[i + 1][0] + dp[i], sum_d[i + 1][1] + sum_max[i])
    

print(dp[-1])

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):
N, K = map(int, input().split())
a_list = list(map(int, input().split()))

point = [[0] * 2 for _ in range(40)]

for i in range(40):
    tmp = 0
    for a in a_list:
        if (a >> (39 - i)) & 1:
            tmp += 1
    
    point[i][0] = tmp * 2 ** (39 - i)
    
    point[i][1] = (N - tmp) * 2 ** (39 - i)


dp = [[-float("inf")] * 2 for _ in range(41)]
dp[0][0] = 0




for i in range(40):
    x = (K >> (39 - i)) & 1

    
    dp[i + 1][0] = dp[i][0] + point[i][x]

    
    
    dp[i + 1][1] = dp[i][1] + max(point[i][0], point[i][1])

    
    
    if x == 1:
        dp[i + 1][1] = max(dp[i][0] + point[i][0], dp[i + 1][1])
print(max(dp[40]))

Solution (Python):
import copy


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    if K == 0:
        print(calc(0, A))
        return
    count = 0
    while True:
        if K < 2 ** (count + 1):
            break
        count += 1
    ans = 0
    A_copy = copy.copy(A)
    while count != -1:
        if (K - ans) < 2 ** count:
            count -= 1
            continue
        zero_count = 0
        one_count = 0
        for a in A_copy:
            if (a >> count) & 1 == 0:
                zero_count += 1
            else:
                one_count += 1
        if one_count < zero_count:
            ans += 2 ** count
        count -= 1
    print(calc(ans, A))


def calc(X, A):
    ans = 0
    for a in A:
        ans += X ^ a
    return ans


if __name__ == "__main__":
    main()

Solution (Python):

import sys

def binary_len(n):
    return len('{0:b}'.format(n))

def count_bits(As):
    bits = [0] * 40
    for a in As:
        for b in range(40):
            if (a & 1 << b) != 0:
                bits[b] += 1
    return bits


def main(N, K, As):
    
    
    bits = count_bits(As)
    

    answer = 0

    k = K
    for digit in reversed(range(0, 40)):
        if (1 << digit) & k == 0:
            answer += (bits[digit]) * (1 << digit)
        elif bits[digit] <= N/2:
            
            k = k - (1 << (digit))
            answer += (N - bits[digit]) * (1 << digit)
        else:
            k = (1 << (digit)) - 1
            answer += (bits[digit]) * (1 << digit)

        
        
        
    return answer


if __name__ == '__main__':
    line = sys.stdin.readline()
    N,K = [int(x) for x in line.strip().split(' ')]

    line = sys.stdin.readline()
    As = [int(x) for x in line.strip().split(' ')]

    assert N == len(As)
    print(main(N, K, As))

Solution (Python):
import math
import sys
from operator import itemgetter








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


MAX_BIT = 41

dp = [[-1 for j in range(2)] for i in range(MAX_BIT+1)]




dp[0][0] = 0
for i in range(1, MAX_BIT+1):
	count = 0
	chk_num = 1 << (MAX_BIT - i)
	for j in range(N):
		if (chk_num & A[j]):
			count += 1
	cost0 = chk_num * count 
	cost1 = chk_num * (N - count) 
	
	if (chk_num & K):
		dp[i][0] = dp[i-1][0] + cost1
		if (dp[i-1][1] == -1):
			dp[i][1] = cost0
		else:
			dp[i][1] = max(dp[i-1][0] + cost0, dp[i-1][1] + cost0, dp[i-1][1] + cost1)
	else:
		dp[i][0] = dp[i-1][0] + cost0
		if (dp[i-1][1] != -1):
			dp[i][1] = max(dp[i-1][1] + cost0, dp[i-1][1] + cost1)
			
print(max(dp[MAX_BIT][0], dp[MAX_BIT][1]))

Solution (Python):

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










maxd = 50
dp = [[-1, -1] for _ in range(maxd+1)]
dp[0][0] = 0

for d in range(maxd):
    s1 = 0
    s0 = 0
    c = 1<<(maxd-d-1)
    for a in al:
        if a&c>0:
            s0 += c
        else:
            s1 += c

    if dp[d][1]!=-1:
        dp[d+1][1] = max(dp[d+1][1], dp[d][1]+max(s1,s0))
    if dp[d][0]!=-1:
        if k&c>0:
            dp[d+1][1] = max(dp[d+1][1], dp[d][0]+s0)
            dp[d+1][0] = max(dp[d+1][0], dp[d][0]+s1)
        else:
            dp[d+1][0] = max(dp[d+1][0], dp[d][0]+s0)

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

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

N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
for upper_bit_bound in range(41,-2,-1):
    if (upper_bit_bound != -1 and not (K & 1 << upper_bit_bound)):
        continue
    fx = 0
    for bit_index in range(41,-1,-1):
        mask = 1 << bit_index
        hit_num = 0
        for a in A:
            if(a & mask):
                hit_num += 1
        nohit_num = N - hit_num
        if (bit_index > upper_bit_bound):
            if(K & mask):
                fx += mask * nohit_num
            else:
                fx += mask * hit_num
        elif(bit_index == upper_bit_bound):
            fx += mask * hit_num
        else:
            fx += mask * max(hit_num, nohit_num)
    ans = max(ans, fx)
print(ans)

Solution (Python):
def d_xxor(N, K, A):
    
    ans = 0
    

    
    bit_stand = [len([1 for a in A if a & (1 << b) != 0]) for b in range(41)]

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

        tmp = 0
        for e in range(40, -1, -1):
            bit_mask = 1 << e

            
            num = bit_stand[e]

            
            if e > d:
                if K & bit_mask != 0:
                    tmp += bit_mask * (N - num)  
                else:
                    tmp += bit_mask * num  
            elif e == d:
                tmp += bit_mask * num  
            else:
                
                
                tmp += bit_mask * max(num, N - num)
        ans = max(ans, tmp)
    return ans

N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
print(d_xxor(N, K, A))

Solution (Python):
def d_xxor(N, K, A):
    
    bit_max = 40
    ans = 0

    for j in range(bit_max, -1, -1):
        power = 1 << j
        
        bit_count_1 = sum(1 for a in A if a & power != 0)

        
        tmp = bit_count_1
        
        if power <= K and bit_count_1 <= N - bit_count_1:
            
            tmp = N - bit_count_1
            K -= power
        
        contribution = power * tmp
        ans += contribution  
    return ans

N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
print(d_xxor(N, K, A))

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

import collections
D = collections.defaultdict(int)

for a in A:
    a2=format(a, 'b')
    for i,a20 in enumerate(a2[::-1]):
        if a20=="1":
            D[i]+=1


K2=format(K, 'b')
K2=K2.zfill(max(D)+1)


Ans=0
n=len(K2)

for i in range(n):
    if K2[i]=="0":
        Ans+=(2**(n-i-1))*D[n-i-1]
    else:
        if D[n-i-1]>N-D[n-i-1]:
            Ans+=(2**(n-i-1))*D[n-i-1]
            break
        else:
            Ans+=(2**(n-i-1))*(N-D[n-i-1])
    
if i<n-1:
    Ans+=sum((2**(n-j-1))*max(D[n-j-1],N-D[n-j-1]) for j in range(i+1,n))

print Ans

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



A01=[[0,0] for i in range(51)]

for keta in range(51):
    A1=0
    A0=0
    for a in A:
        if a & (1<<keta)==0:
            A1+=1<<keta
        else:
            A0+=1<<keta

    A01[keta]=[A0,A1]



def ANS(keta,limit):
    
    if keta==-1:
        return 0

    if limit==1:               
        return max(A01[keta][0],A01[keta][1])+ANS(keta-1,1)

    if limit==0:
        if K & (1<<keta)==0:
            return A01[keta][0]+ANS(keta-1,0)
        else:
            return max(A01[keta][0]+ANS(keta-1,1),A01[keta][1]+ANS(keta-1,0))

print(ANS(50,0))

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



A01=[[0,0] for i in range(51)]

for keta in range(51):
    A1=0
    A0=0
    for a in A:
        if a & (1<<keta)==0:
            A1+=1<<keta
        else:
            A0+=1<<keta

    A01[keta]=[A0,A1]



def ANS(keta,limit):
    
    if keta==-1:
        return 0

    if limit==1:               
        return max(A01[keta][0],A01[keta][1])+ANS(keta-1,1)

    if limit==0:
        if K & (1<<keta)==0:
            return A01[keta][0]+ANS(keta-1,0)
        else:
            return max(A01[keta][0]+ANS(keta-1,1),A01[keta][1]+ANS(keta-1,0))

print(ANS(50,0))

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



def ANS(keta,limit):
    
    if keta==-1:
        return 0

    A1=0
    A0=0
    for a in A:
        if a & (1<<keta)==0:
            A1+=1<<keta
        else:
            A0+=1<<keta
    
    if limit==1:               
        return max(A0,A1)+ANS(keta-1,1)

    if limit==0:
        if K & (1<<keta)==0:
            return A0+ANS(keta-1,0)
        else:
            return max(A0+ANS(keta-1,1),A1+ANS(keta-1,0))

print(ANS(50,0))

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
h = [[0, 0] for _ in range(41)]
b = list(map(int, bin(k)[2:].zfill(41)))
for i in a:
    for x, y in enumerate(map(int, bin(i)[2:].zfill(41))):
        h[x][y] += 1

ans = 0
ctr = 0
hm = [max(x, y)*2**(40-i) for i, [x, y] in enumerate(h)]
for i, v in enumerate(b):
    if not v:
        ctr += h[i][1]*2**(40-i)
    else:
        ans = max(ans, ctr+h[i][1]*2**(40-i)+sum(hm[i+1:]))
        ctr += h[i][0]*2**(40-i)
print(max(ans, ctr))

Solution (Python):
N, K = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
C = [[0]*2 for i in range(40)]
for i in range(40):
  cc = 0
  for a in A:
    if (a>>(39-i))&1:
      cc += 1
  C[i][0] = cc * 2**(39-i)
  C[i][1] = (N-cc) * 2**(39-i)
INF = float("inf")
dp = [[-INF]*2 for i in range(41)]
dp[0][0] = 0
for i in range(40):
  d = (K>>(39-i))&1
  dp[i+1][0] = dp[i][0] + C[i][d]
  dp[i+1][1] = dp[i][1] + max(C[i])
  if d == 1:
    dp[i+1][1] = max(dp[i][0] + C[i][0], dp[i+1][1])
print(max(dp[40]))

Solution (Python):
N, K = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
C = [[0]*2 for i in range(40)]
for i in range(40):
  cc = 0
  for a in A:
    if a & (2**(39-i)):
      cc += 1
  C[i][0] = cc * 2**(39-i)
  C[i][1] = (N-cc) * 2**(39-i)
INF = float("inf")
dp = [[-INF]*2 for i in range(41)]
dp[0][0] = 0
for i in range(40):
  d = (K>>(39-i))&1
  dp[i+1][0] = dp[i][0] + C[i][d]
  dp[i+1][1] = dp[i][1] + max(C[i])
  if d == 1:
    dp[i+1][1] = max(dp[i][0] + C[i][0], dp[i+1][1])
print(max(dp[40]))

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

V = [0]*41
for a in A:
    for i in range(40,-1,-1):
        if a%2 == 0:
            pass
        else:
            V[i] += 1
        a //= 2
        if a == 0:
            break
W = [0]*41
for i in range(40,-1,-1):
    if K%2 == 0:
        pass
    else:
        W[i] += 1
    K //= 2
    if K == 0:
        break
ans = 0
check = 0
dp = [[-1]*2 for _ in range(42)]
dp[0][0] = 0
for i in range(41):
    if dp[i][1] != -1:
        dp[i+1][1] = dp[i][1] + (2**(40-i))*max(V[i], N-V[i])
    if dp[i][0] != -1:
        if W[i] == 1:
            dp[i+1][1] = max( dp[i+1][1], dp[i][0]+(2**(40-i))*V[i] )
    if dp[i][0] != -1:
        if W[i] == 1:
            dp[i+1][0] = dp[i][0] + (2**(40-i))*(N-V[i])
        else:
            dp[i+1][0] = dp[i][0] + (2**(40-i))*V[i]
print( max( dp[-1][0], dp[-1][1]))

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

V = [0]*41
for a in A:
    for i in range(40,-1,-1):
        if a%2 == 0:
            pass
        else:
            V[i] += 1
        a //= 2
        if a == 0:
            break
W = [0]*41
for i in range(40,-1,-1):
    if K%2 == 0:
        pass
    else:
        W[i] += 1
    K //= 2
    if K == 0:
        break
ans = 0
check = 0
dp = [[-1]*2 for _ in range(42)]
dp[0][0] = 0
for i in range(41):
    if dp[i][1] != -1:
        dp[i+1][1] = dp[i][1] + (2**(40-i))*max(V[i], N-V[i])
    if dp[i][0] != -1:
        if W[i] == 1:
            dp[i+1][1] = max( dp[i+1][1], dp[i][0]+(2**(40-i))*V[i] )
    if dp[i][0] != -1:
        if W[i] == 1:
            dp[i+1][0] = dp[i][0] + (2**(40-i))*(N-V[i])
        else:
            dp[i+1][0] = dp[i][0] + (2**(40-i))*V[i]
print( max( dp[-1][0], dp[-1][1]))

Solution (Python):
n,k=map(int,input().split())
buf=input().split()
a=[None for i in range(n)]
for i in range(n):
    a[i]=int(buf[i])
cnt=[0 for i in range(45)]
for i in a:
    for j in range(45):
        cnt[j]+=i%2
        i//=2
        if i==0:
            break
res=0
for i in range(44,-1,-1):
    toadd=2**i
    if toadd>k:
        continue
    if cnt[i]<=n//2 and res+toadd<=k:
        res+=toadd
ress=0
for i in a:
    ress+=res^i
print(ress)

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


from collections import defaultdict
counter=defaultdict(int)


def makebit(a):
    return bin(a)[2:]


def count(a):
    l=len(a)
    for i in range(1,l+1):
        if a[-i]=='1':
            counter[i]+=1
    return


for i in range(len(a)):
    count(makebit(a[i]))




kbit=makebit(k)






if len(counter)>0:
    maxlenth=max(counter)
elif len(counter)==0:
    maxlenth=0


maxlenth=max(maxlenth,len(kbit))    



for i in range(1,1+maxlenth):
    if counter[i]==0:
        counter[i]=0


kbit='0'*(maxlenth-len(kbit))+kbit



kaijo=[]
kaiji=1
for i in range(maxlenth+1):
    kaijo.append(kaiji)
    kaiji*=2




def search(kbit,default,ans,before,counter):
    
    if kbit.count('1')==0:
        dlenth=0
        
        
    elif kbit.index('1')==len(kbit)-1:
        dlenth=1
        
        for keta in counter:
            if keta>=before:continue
            elif keta>dlenth:
                default+=counter[keta]*kaijo[keta-1]
            elif keta==dlenth:
                default+=max(n-counter[keta],counter[keta])*kaijo[keta-1]
        if default>ans:ans=default
        return ans
    
    
    
    
    elif kbit.count('1')>0:dlenth=len(kbit)-kbit.index('1')
    
    
    now=default
    
    
    newcounter=counter.copy()
    
       
    for keta in counter:
        if keta>before:continue
        elif keta>dlenth:
            
            
            default+=counter[keta]*kaijo[keta-1]
            now+=counter[keta]*kaijo[keta-1]
            newcounter.pop(keta)
            
        elif keta==dlenth:
            
            default+=(n-counter[keta])*kaijo[keta-1]
            now+=counter[keta]*kaijo[keta-1]
            newcounter.pop(keta)
            
        elif keta<dlenth:
            
            now+=max(n-counter[keta],counter[keta])*kaijo[keta-1]
    
    if now>ans:ans=now
    if dlenth==0:return ans
    
    idx=kbit.index('1')
    kbit=kbit[idx+1:]
    
    
    
    
    
    return search(kbit,default,ans,dlenth,newcounter)
    
print(search(kbit,0,0,maxlenth+1,counter))

Solution (Python):
N, K = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
C = [0]*40
for i in range(40):
  for a in A:
    if a & (2**(39-i)):
      C[i] += 1
INF = float("inf")
dp = [[-INF]*2 for i in range(41)]
dp[0][0] = 0
for i in range(40):
  if K & (2**(39-i)):
    temp1 = dp[i][0] + 2**(39-i)*C[i]
    temp2 = dp[i][1] + 2**(39-i)*max(C[i],N-C[i])
    dp[i+1][1] = max(temp1, temp2)
    dp[i+1][0] = dp[i][0] + 2**(39-i)*(N-C[i])
  else:
    dp[i+1][1] =  dp[i][1] + 2**(39-i)*max(C[i],N-C[i])
    dp[i+1][0] = dp[i][0] + 2**(39-i)*C[i]
print(max(dp[40]))

Solution (Python):
import math


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

    X = 0
    if K != 0:
        for digit in range(40, -1, -1):
            if digit > math.log2(K) + 1:
                continue

            zero_n = 0
            one_n = 0
            for a in A:
                if (a >> digit) & 1:
                    one_n += 1
                else:
                    zero_n += 1

            if one_n < zero_n and (X + (1 << digit)) <= K:
                X += (1 << digit)
    else:
        X = 0

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

    print(ans)

Solution (Python):
import sys
def main():
    n,k = map(int, input().split())
    a = [[0]*40 for _ in range(n)]
    a_ = []
    for i,x in enumerate(map(int, input().split())):
      j=0
      while x>0:
        if x%2==1: a[i][j]=1
        x = x//2
        j += 1
    ans=0
    x = 0
    for i in range(39,-1,-1):
      b = 0
      for y in a:
        b+=y[i]
      if b<=n//2 and x+2**i<=k:
        ans += (n-b)*2**i
        x+=2**i
      else:
        ans += b*2**i
          
    print(ans)
    
if __name__=="__main__":
    main()

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

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

B = [0]*41

for i in range(N):
    for j in range(41):
        if (A[i]>>j) & 1 == 1:
            B[j] += 1


C = [0]*41
for i in range(41):
    if (K>>i) & 1 == 1:
        C[i] += 1

D =[]
for i in range(40,-1,-1):
    count = 0
    if C[i] == 1:
        count += B[i]*2**i
        for k in range(40,i,-1):
            if C[k] == 0:
                count += B[k]*2**k
            else:
                count += (N-B[k])*2**k
        for j in range(i):
            if N-B[j] >= B[j]:
                count += (N-B[j])*2**j
            else:
                count += B[j]*2**j
    D.append(count)
score = 0
for i in range(41):
    if C[i] == 0:
        score += B[i]*2**i
    else:
        score += (N-B[i])*2**i
D.append(score)

print(max(D))

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,k = LI()
    a = LI()
    t = []
    for i in range(42):
        ii = 2**i
        b = 0
        for c in a:
            if c & ii:
                b += 1
        t.append([b*ii,(n-b)*ii])

    fm = {}
    def f(i,mf):
        if i < 0:
            return 0
        fk = (i,mf)
        if fk in fm:
            return fm[fk]
        ii = 2**i
        r = 0
        if k & ii or not mf:
            b = f(i-1,mf)
            b += t[i][1]
            if r < b:
                r = b
            b = f(i-1,False)
            b += t[i][0]
            if r < b:
                r = b
        elif mf:
            b = f(i-1,mf)
            b += t[i][0]
            if r < b:
                r = b
        fm[fk] = r
        return r

    mi = 0
    for i in range(1,42):
        ii = 2**i
        if ii > k:
            mi = i - 1
            break
    r = f(40,True)

    return r



print(main())

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
K=str(format(k,'b'))
M=str(format(max(a),'b'))
x=max(len(K),len(M))
K=str(format(k,'b').zfill(x))
l=[]
for i in range(n):
  l.append(str(format(a[i],'b').zfill(x)))
ctMz=0
for z in range(len(K)):
  if K[z]=='0':
    ctMz+=1
  else:
    break

l2=[]
l2=['0' for b in range(x)]
ct=0
for j in range(x):
  ctz=0
  cto=0
  for m in range(n):
    if l[m][j]=='0':ctz+=1
    else:cto+=1
  if j+1<=ctMz:
    ct+=(2**(x-j-1))*cto
    l2[j]='0'
  else:
    if ctz>cto:
      l2[j]='1'
      if int(K)>=int(''.join(l2)):
        ct+=(2**(x-j-1))*ctz
      else:
        ct+=(2**(x-j-1))*cto
        l2[j]='0'
    else:
      ct+=(2**(x-j-1))*cto
      l2[j]='0'
print(ct)