Numero che ricorre un numero dispari di volte

Lezione 10 di 17 del corso Manipolazione dei bit di Coddy.

Ricordi la sfida che hai risolto nella lezione «Operatore XOR», in cui abbiamo usato le proprietà di XOR. La domanda che risolveremo in questa lezione è molto simile a quella sfida. Quindi, il problema che esamineremo è:

Trova l'elemento che compare un numero dispari di volte nell'array dato.

Ti verrà dato un array contenente alcuni elementi interi. Tra questi elementi, tutti gli altri compaiono un numero pari di volte, tranne un elemento.

Supponiamo di avere un array int Arr[11] = { 2, 5, 6, 6, 6, 4, 5, 2, 5, 4, 5}.

In questo array,

'2' compare due volte (pari).
'5' compare quattro volte (pari).
'6' compare tre volte (dispari).
'4' compare due volte (pari).

Quindi, in questo caso il numero «6» è quello che compare un numero dispari di volte. Ed è proprio questo che dobbiamo trovare nella domanda: il numero che compare un numero dispari di volte nell'array.

Come abbiamo visto nella lezione sull'operatore «XOR», per un numero «x»:

x ⊕ x = 0 (dove il simbolo '⊕' rappresenta l'operazione XOR)
x ⊕ 0 = x

Quindi, usando la prima proprietà, tutti gli elementi che compaiono un numero pari di volte, sottoposti all'operazione XOR, daranno come risultato 0; usando la seconda proprietà, rimarrà il numero che compariva un numero dispari di volte.

In sostanza, applicando XOR a tutti gli elementi dell'array si otterrà il risultato. Ecco fatto, questa è la soluzione del problema. Facile, vero?

La complessità temporale di questo problema è O(n), poiché dobbiamo attraversare l'intero array e applicare XOR a tutti i suoi elementi.

Sfida

Facile

Completa la funzione "OddElement" per restituire l'elemento che è apparso un numero dispari di volte nell'array fornito. Usa l'operatore XOR per risolvere questo problema.

Provalo tu

#include <iostream>
#include <vector>
using namespace std;

int OddElement(vector<int> arr) {
    // Scrivi il codice qui
}

Tutte le lezioni di Manipolazione dei bit

1Introduzione e basi

Cos’è la manipolazione dei bit?Perché serve la manipolazione dei bit?Numeri binari e decimali Operatori NOT e OR Operatore AND Operatore XOR Operatori di shift a destra e a sinistra Riepilogo degli operatori bitwise

2Algoritmi sui bit

Potenza di 2Numero che ricorre un numero dispari di volteNumero di bit impostati Rotazione dei bit di un numero I Rotazione dei bit di un numero II

3Sfide pratiche

Tina e l’assegnazione dei bit XORty Trova K Trova la somma minima

Esercitati da solo: Compilatore C++ online