Question

#2630 permd

int PermD(int a[], int n)

Funcția primește ca parametru un vector a = (a1, a2, ..., an) de lungime n care memorează toate valorile distincte din mulțimea {1, 2,..., n-1}, dar exact una din aceste valori apare în vector de două ori. Funcția trebuie să returneze valoarea care apare de două ori.

Restricții și precizări
1 ≤ n ≤ 1.000.000
Numele funcției este PermD
Întotdeauna va exista exact o valoare care apare de două ori
Elementele din vector sunt indexate de la 1 la n



Exemplu
Dacă n = 6 și a = (3,5,2,1,2,4) atunci PermD(a, n) va returna valoarea 2.

Important
Soluţia propusă va conţine definiţia funcţiei cerute. Prezenţa în soluţie a altor instrucţiuni poate duce erori de compilare sau de execuţie care vor avea ca efect depunctarea soluţiei.

Answer 1

#include <bitset>

bitset<1000000>b;

int PermD(int a[], int n)

{

   int c;

   for (int i=1; i<n; ++i)

       if(b[a[i]]==0) b[a[i]]=1;

       else { c=a[i]; break;  }

   return c;

}