trouver le numéro qui ne se répète pas dans O (n) O (1) Espace

Question

pour commencer, j'ai eu un coup d'œil à ces questions:

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

celui-ci différent:

donné un tableau d'entiers non triés avec un numéro unique et les nombres de repos répéter 3 fois, soit:

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

nous devons trouver ce numéro unique dans O (n) et O (1) Espace

NOTE: ce n'est pas un devoir, juste que je une bonne question, je suis tombé sur

Answer 1

Qu'en est-ce un:

Idée: faire mod plus bitwise 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); 
}