Geek asks and answers

Find a number that does not repeat in O (n) time O (1) space

To start, I looked at these questions:

Given an array of integers where some numbers are repeated 1 time, some numbers are repeated 2 times, and only one number is repeated 3 times, how do you find a number that is repeated 3 times

Algorithm for finding two repeating numbers in an array without sorting

this is different:

an unsorted array of integers with one unique number is given, and the remaining numbers are repeated 3 times, i.e.:

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

we need to find this singular in O (n) time and O (1) space

NOTE: this is not homework, I just have a good question that I met

+5
source share
1 answer

How about this:

Idea: do a bitwise addition of 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);
}
+7

More articles:


All Articles