# Ois\_duplicato 70/100

**URL:** <https://forum.olinfo.it/t/ois-duplicato-70-100/4690>\
**Category:** Aiuto\
**Created:** [28 Giugno 2017, 9:09pm UTC](https://forum.olinfo.it/t/ois-duplicato-70-100/4690 "2017-06-28T21:09:01Z")\
**Posts on this page:** 13\
**Page:** 1

<div class="post-metadata">

**Author:** ![Think.Different](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/t/ea5d25/32.png) [@Think.Different](https://forum.olinfo.it/u/Think.Different)\
**Post date:** [28 Giugno 2017, 9:09pm UTC](https://forum.olinfo.it/t/ois-duplicato-70-100/4690/1 "2017-06-28T21:09:01Z")

</div>

Salve a tutti,  
ultimamente ho provato a sviluppare l’algoritmo risolutivo del problema “**Duplicato mancante (duplicato)**”.  
Durante lo sviluppo dell’algoritmo non ho riscontrato alcuna difficoltà, provando nel mio PC il programma con gli esempi di prova, gli output sono esatti… però nelle varie Sottoposizioni (comprese quelle di prova) prendo 0/100 per output non corretto…  
Qui potete trovare il mio codice : [https://pastebin.com/fiugCdXr](https://pastebin.com/fiugCdXr)

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [28 Giugno 2017, 9:14pm UTC](https://forum.olinfo.it/t/ois-duplicato-70-100/4690/2 "2017-06-28T21:14:53Z")

</div>

Cosi a prima vista prova a inizializzare pos e foglio potrebbe essere quello 🙂

---

<div class="post-metadata">

**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\
**Post date:** [28 Giugno 2017, 9:25pm UTC](https://forum.olinfo.it/t/ois-duplicato-70-100/4690/3 "2017-06-28T21:25:26Z")

</div>

Il bug sta nella tua funzione `trova`, in cui chiami `std::count(P, P + N, P[i])`, mentre dovresti chiamare `std::count(P, P + 2 * N, P[i])`. Altra cosa che non tenevi in considerazione è il fatto che la `count` considera anche l’elemento corrente, quindi per l’elemento di cui manca la copia ritorna 1 e non 0.

Mi sono preso la briga di riscivere la tua funzione `trova`:

```
int trova(int N, int P[])
{
    for(int i = 0; i < 2 * N; i++)
    {
        if(std::count(P, P + 2 * N, P[i]) == 1)
            return P[i];
    }
    return -1;
}

```

Questo algoritmo comunque non permette di andare oltre i 70 punti, perchè ha complessità \mathcal O(N^2) e va quindi fuori tempo limite, mentre la complessità richiesta è al più \mathcal O(NlogN). Esiste anche un algoritmo in \mathcal O(N), ma in questo caso non era richiesto.

Dario

---

<div class="post-metadata">

**Author:** ![Think.Different](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/t/ea5d25/32.png) [@Think.Different](https://forum.olinfo.it/u/Think.Different)\
**Post date:** [28 Giugno 2017, 9:50pm UTC](https://forum.olinfo.it/t/ois-duplicato-70-100/4690/4 "2017-06-28T21:50:38Z")

</div>

Esattamente 70/100… mi è bastato cambiare “N” in “N\*2-1” ed ho ottenuto 70/100.  
Ma tu come facevi a sapere che avrei preso 70/100 ? 😂

---

<div class="post-metadata">

**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\
**Post date:** [28 Giugno 2017, 9:52pm UTC](https://forum.olinfo.it/t/ois-duplicato-70-100/4690/5 "2017-06-28T21:52:16Z")

</div>

Ti ho molto ignorantemente rubato il codice e lo ho sottomesso con le correzioni

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [28 Giugno 2017, 9:52pm UTC](https://forum.olinfo.it/t/ois-duplicato-70-100/4690/6 "2017-06-28T21:52:31Z")

</div>

Algoritmo in O (n) ?Usi una map?

---

<div class="post-metadata">

**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\
**Post date:** [28 Giugno 2017, 9:53pm UTC](https://forum.olinfo.it/t/ois-duplicato-70-100/4690/7 "2017-06-28T21:53:46Z")

</div>

Con la map viene \mathcal O(NlogN), con una hashmap verrebbe \mathcal O(N) ma con fattori costanti bruttarelli. Esiste una soluzione in \mathcal O(N) elegantissima basata sullo `^`

---

<div class="post-metadata">

**Author:** ![Think.Different](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/t/ea5d25/32.png) [@Think.Different](https://forum.olinfo.it/u/Think.Different)\
**Post date:** [28 Giugno 2017, 9:55pm UTC](https://forum.olinfo.it/t/ois-duplicato-70-100/4690/8 "2017-06-28T21:55:49Z")

</div>

Ah si avevo letto qualcosa del genere…  
Ma dovrebbe essere lo XOR di quale valore ?

---

<div class="post-metadata">

**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\
**Post date:** [28 Giugno 2017, 9:58pm UTC](https://forum.olinfo.it/t/ois-duplicato-70-100/4690/9 "2017-06-28T21:58:49Z")

</div>

L’idea è quella di partire da a \oplus a = 0 e a \oplus 0 = a, dove \oplus indica lo xor tra due valori. Quindi se facciamo lo xor di tutti i valori in ingresso ogni valore che è presente due volte si annulla, mentre il risultato sarà proprio il valore dell’elemento presente una volta sola.

---

<div class="post-metadata">

**Author:** ![Think.Different](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/t/ea5d25/32.png) [@Think.Different](https://forum.olinfo.it/u/Think.Different)\
**Post date:** [28 Giugno 2017, 10:08pm UTC](https://forum.olinfo.it/t/ois-duplicato-70-100/4690/10 "2017-06-28T22:08:43Z")

</div>

Quindi all’interno del ciclo dovrei fare “**P[i] ^ P[i]**” ?

---

<div class="post-metadata">

**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\
**Post date:** [28 Giugno 2017, 10:11pm UTC](https://forum.olinfo.it/t/ois-duplicato-70-100/4690/11 "2017-06-28T22:11:43Z")

</div>

No, quello che devi fare è mantenere un unico valore che è lo xor di tutti i valori in ingresso, una cosa del tipo di V = P[0] \oplus P[1] \oplus \ldots \oplus P[N - 1]. V sarà il risultato.

---

<div class="post-metadata">

**Author:** ![Think.Different](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/t/ea5d25/32.png) [@Think.Different](https://forum.olinfo.it/u/Think.Different)\
**Post date:** [28 Giugno 2017, 10:20pm UTC](https://forum.olinfo.it/t/ois-duplicato-70-100/4690/12 "2017-06-28T22:20:09Z")

</div>

Grazie @dp_1 dell’aiuto… sono riuscito ad ottenere 100/100.  
Pero’ mi piacerebbe sapere come è possibile trovare il risultato con lo XOR… se no non imparo niente e i 100 pt non hanno valore 😉…

---

<div class="post-metadata">

**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\
**Post date:** [29 Giugno 2017, 8:56am UTC](https://forum.olinfo.it/t/ois-duplicato-70-100/4690/13 "2017-06-29T08:56:24Z")

</div>

In ingresso hai una lista di interi a\_0, a\_1, b\_0, b\_1, c\_0, c\_1, \ldots, z\_0, dove le coppie a\_0, a\_1 e simili indicano due valori identici, mentre z\_0 è il valore che è presente una sola volta. La lista in ingresso non è necessariamente in quest’ordine, ma ce ne importa ben poco. Facendo lo xor di tutti i valori in questa lista le coppie del tipo di a\_0, a\_1 si annulleranno, perchè a \oplus a = 0, quindi alla fine otterremo V = 0 \oplus 0 \oplus 0 \ldots \oplus z\_0 = z\_0, che non è altro che il risultato richiesto.