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

Question

for starters, I did have a look at these 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

this one different:

given an unsorted array of integers with one unique number and the rest numbers repeat 3 times, i.e.:

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

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

NOTE: this is not a homework, just I an nice question I came across

related: [Finding an element in an array where every element is repeated odd number of times and only one appears once](http://stackoverflow.com/q/7338070/4279) — jfs, Aug 09 '12 at 14:11

score 9 · Accepted Answer · edited Aug 09 '12 at 13:51

9

What about this one:

Idea: do bitwise 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);
}

edited Aug 09 '12 at 13:51

Paul R

208,748
37
389
560

answered Aug 09 '12 at 12:55

2

I just compiled your algorithm and it seems to work and you use only bitwise operations. care to explain how it works ? – candyman Aug 09 '12 at 13:14
@candyman: Take binary representation of each number in the list. Count how many times each bit occurs (modulo 3). For each counter, that is equal to one, set corresponding bit in the result value. Example: {4,5,3, 5,3,4, 1, 4,3,5 } -> bit0=7=1, bit1=3=0, bit2=6=0 -> result=1 – Evgeny Kluev Aug 09 '12 at 13:18
aah got it, thanks Evgeny, your solution is also correct then – candyman Aug 09 '12 at 13:22
yes Eugeny suggests basically the same approach, I just use bitwise airithmetic directly – Aug 09 '12 at 13:24

score 0 · Answer 2 · edited Sep 06 '18 at 09:21

This solution works for all inputs. The idea is to extract the bits of an integer from array and add to respective 32bit bitmap 'b' (implemented as 32byte array to represent 32bit no.)

unsigned int a[7] = {5,5,4,10,4,9,9};
unsigned int b[32] = {0};  //Start with zeros for a 32bit no.
main1() {
    int i, j;
    unsigned int bit, sum =0 ;
    for (i=0;i<7; i++) {
        for (j=0; j<32; j++) { //This loop can be optimized!!!!
            bit = ((a[i] & (0x01<<j))>>j); //extract the bit and move to right place
            b[j] += bit; //add to the bitmap array
        }
    }
    for (j=0; j<32; j++) {
        b[j] %= 2;     //No. repeating exactly 2 times.
        if (b[j] == 1) {
            sum += (unsigned int) pow(2, j); //sum all the digits left as 1 to get no
            //printf("no. is %d", sum);
        }
    }
    printf("no. is %d", sum);
}

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

2 Answers2