Trova numero univoco tra 3n + 1 numeri

Question

Mi è stata posta questa domanda in un'intervista.

Dato che ci sono 3n + 1 numeri. n di questi numeri si verificano in terzine, solo 1 si verifica una volta sola. Come troviamo il numero univoco in tempo lineare, cioè O (n)? I numeri non sono ordinati.

Nota che, se ci fossero 2n + 1 numeri, di cui n si verificano in coppia, potremmo solo XOR tutti i numeri per trovare quello unico. L'intervistatore mi ha detto che può essere fatto manipolando bit.

Answer 1

1. contare il numero di volte in cui ogni bit si verifica nel set di 3n + 1 numeri.
2. Riduci ogni numero di bit modulo 3.
3. Ciò che resta è la sequenza di bit del singolo numero.

Oh, dreamzor (sopra) mi ha battuto su di esso.

Answer 2

È possibile inventare un XOR 3nary (chiamarlo XOR3) operazione che opera in base 3 anziché in base 2 e prende semplicemente ogni 3 cifre modulo 3 (quando di consueto XOR prende 2 cifre modulo 2).

Quindi, se si XOR3 tutti i numeri (convertendoli prima in 3nari) in questo modo, verrà lasciato con il numero univoco (in base 3 quindi sarà necessario riconvertirlo).

La complessità non è esattamente lineare, tuttavia, poiché le conversioni da/verso base 3 richiedono un tempo logaritmico aggiuntivo. Tuttavia, se l'intervallo di numeri è costante, anche il tempo di conversione è costante.

Codice in C++ (intenzionalmente verbose):

vector<int> to_base3(int num) { 
    vector<int> base3; 
    for (; num > 0; num /= 3) { 
    base3.push_back(num % 3); 
    } 
    return base3; 
} 

int from_base3(const vector<int> &base3) { 
    int num = 0; 
    for (int i = 0, three = 1; i < base3.size(); ++i, three *= 3) { 
    num += base3[i] * three; 
    } 
    return num; 
} 

int find_unique(const vector<int> &a) { 
    vector<int> unique_base3(20, 0); // up to 3^20 
    for (int num : a) { 
    vector<int> num_base3 = to_base3(num); 
    for (int i = 0; i < num_base3.size(); ++i) { 
     unique_base3[i] = (unique_base3[i] + num_base3[i]) % 3; 
    } 
    } 

    int unique_num = from_base3(unique_base3); 
    return unique_num; 
} 

int main() { 
    vector<int> rands { 1287318, 172381, 5144, 566546, 7123 }; 
    vector<int> a; 
    for (int r : rands) { 
    for (int i = 0; i < 3; ++i) { 
     a.push_back(r); 
    } 
    } 
    a.push_back(13371337); // unique number 

    random_shuffle(a.begin(), a.end()); 

    int unique_num = find_unique(a); 
    cout << unique_num << endl; 
} 

Answer 3

byte [] oneCount = new byte [32]; 

int [] test = {1,2,3,1,5,2,9,9,3,1,2,3,9}; 

for (int n: test) { 
    for (int bit = 0; bit < 32; bit++) { 
     if (((n >> bit) & 1) == 1) { 
      oneCount[bit]++; 
      oneCount[bit] = (byte)(oneCount[bit] % 3); 
     } 
    } 
} 

int result = 0; 
int x = 1; 

for (int bit = 0; bit < 32; bit++) { 
    result += oneCount[bit] * x; 
    x = x << 1; 
} 

System.out.print(result); 

Sembra che mentre stavo codifica, altri hanno dato l'idea principale