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

<syntaxhighlight lang="python" line>

1. 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

1. 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()))

1. Apelăm funcția

result = FrecvImp(numere)

1. Deschidem fișierul de ieșire și scriem rezultatul

with open('frecvimp.out', 'w') as iesire:

   iesire.write(str(result))

</syntaxhighlight>