número hallazgo que no se repite en O (n) tiempo O (1) Espacio

Question

para empezar, tuve un vistazo a las siguientes preguntas:

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

éste diferente:

dado un vector sin clasificar de números enteros con un número único y los números de descanso repiten 3 veces, es decir :

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

tenemos que encontrar este número único en el tiempo O (n) y O (1) Espacio

NOTA: esto no es una tarea, acabo una buena pregunta que me encontré con

Answer 1

¿Qué pasa con este uno:

Idea: hacer adición bit a bit 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); 
}