2714 - Frecv Imp

Cerinţa

Se dă un șir format din n numere naturale. Toate valorile putere a lui 2 din acest șir au frecvență pară, cu o singură excepție. Determinați această valoare – putere a lui 2 cu frecvență impară.

Date de intrare

Fișierul de intrare frecvimp.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

Date de ieşire

Fișierul de ieșire frecvimp.out va conține pe prima linie numărul p, reprezentând singura valoare din șirul dat care este putere a lui 2 și are frecvență impară.

Restricții și precizări

• 1 les; n ⩽ 1.000.000
• numerele de pe a doua linie a fișierului de intrare sunt naturale, nenule și mai mici decât $9223372036854775807$
• $9223372036854775807=2⁶³-1$

Exemplu

frecvimp.in

10

41 235 64 41 512 64 1488 512 361 512

frecvimp.out

512

Explicație

În fișierul de intrare sunt 2 puteri ale lui 2, 64 și 512, dintre care 512 apare de 3 ori.

Rezolvare

# Definim funcția
def FrecvImp(n):
    # Inițializăm un dicționar gol
    frec = {}
    # Parcurgem lista de numere
    for n in n:
        # Dacă numărul nu se află încă în dicționar, îl adăugăm cu frecvența 0
        if n not in frec:
            frec[n] = 0
        # Incrementăm frecvența numărului curent
        frec[n] += 1

    # Parcurgem dicționarul
    for n in frec:
        # Verificăm dacă frecvența numărului curent este impară și dacă numărul este o putere a lui 2
        if frec[n] % 2 == 1 and (n & (n - 1) == 0):
            # Dacă găsim un astfel de număr îl returnăm
            return n

# Deschidem fișierul de intrare și citim datele
with open('frecvimp.in', 'r') as intrare:
    n = int(intrare.readline())
    # Citim a doua linie, o împărțim în cuvinte separate prin spații și convertim fiecare cuvânt la int
    numere = list(map(int, intrare.readline().split()))

# Apelăm funcția
result = FrecvImp(numere)

# Deschidem fișierul de ieșire și scriem rezultatul
with open('frecvimp.out', 'w') as iesire:
    iesire.write(str(result))