Fundnummer, die in O (n) O (1) Raum

Question

für den Anfang nicht wiederholt, habe ich bei diesen Fragen einen Blick:

Given an array of integers where some numbers repeat 1 time, some numbers repeat 2 times and only one number repeats 3 times, how do you find the number that repeat 3 times

Algorithm to find two repeated numbers in an array, without sorting

dieses anders:

eine unsortierte Array von ganzen Zahlen mit einer eindeutigen Nummer und die übrigen Zahlen 3-mal wiederholen gegeben, dh:

{4,5,3, 5,3,4, 1, 4,3,5 } 

müssen wir diese eindeutige Nummer in O (n) Zeit und O (1) Raum finden

HINWEIS: dies ist keine Hausaufgaben, ich habe gerade eine nette Frage, die ich über

kam

Answer 1

Was darüber one:

Idee: bitweise Addition mod 3

#include <stdio.h> 

int main() { 
    int a[] = { 1, 9, 9, 556, 556, 9, 556, 87878, 87878, 87878 }; 
    int n = sizeof(a)/sizeof(int); 
    int low = 0, up = 0; 

    for(int i = 0; i < n; i++) { 
     int x = ~(up & a[i]); 
     up &= x; 
     x &= a[i]; 
     up |= (x & low); 
     low ^= x; 
    } 
    printf("single no: %d\n", low); 
}