Problemi 144
Kërkesa
Jepet një varg me numra natyrorë \(A_1, A_2, ... , A_N\). Ju mund të zgjidhni një numër natyror X dhe të bëni me të veprimin bitwise XOR me secilin nga numrat e vargut, pastaj të merrni shumën e këtyre numrave. Sa është vlera më e vogël e mundshme e kësaj shume.
Referenca: https://www.codechef.com/LTIME71B/problems/MINARRS
Shembull
$ cat input.txt
3
5
2 3 4 5 6
4
7 7 7 7
3
1 1 3
$ python3 prog.py < input.txt
14
0
2
Në rastin e parë mund të zgjedhin X = 6, dhe vargu bëhet (4, 5, 2, 3, 0).
Në rastin e dytë mund të zgjedhim X = 7 dhe të gjithë numrat e vargut bëhen 0.
Në rastin e tretë mund të zgjedhim X = 1, dhe vargu bëhet (0, 0, 2), shuma e të cilit është 2.
Zgjidhja
for _ in range(int(input())):
n = int(input())
L = [format(int(i), '030b') for i in input().split()]
X = ['0' for i in range(30)]
for i in range(30):
c = 0
for j in range(n):
if L[j][i] == '1':
c += 1
if c > n - c:
X[i] = '1'
x = int(''.join(X), 2)
s = 0
for a in L:
s += int(a,2) ^ x
print(s)