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)