Question

Să se scrie funcția cu următorul antet:

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.
Stiti ce este gresit la aceasta solutie(primesc 50 de puncte)?int PermD(int a[],int n)
{int s=0,S;
for(int i=1;i<=n;i++)
s+=a[i];
S=n*(n+1)/2-s;
return n-S;
}

Answer 1

Răspuns:

///vector de numarare

#include <bitset>  

bitset<1000000>b;

 //vectorul b retine valori de 0 si 1

//0 daca nu a aparut in vectorul a

//1 daca a aparut o data

int PermD(int a[], int n)  

{  

  int c;  

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

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

     ///in cazul in care e diferit de 0

    ///inseamna ca a aparut cel putin o data

      else { c=a[i]; break;  }  ///daca am gasit o valoare

  ///care apare de 2 ori opresc for-ul

  return c;  //returnez valoarea care apare de 2 ori

}

Explicație: