Tuesday, April 8, 2014

Find single number!!

Given an array containing integers, where each number occurs three times except for one number which occurs only once, find the number which occurs only once.
Couldnt think of a way to use XOR for this. XOR works fine when all numbers appear twice and only one of them appears once.
But we can still use some bit magic for this question.
Lets consider ith bit of all numbers. If we count the total number of one's in the ith bit for all numbers and later divide this number by 3, we can get the ith bit of the desired number. So lets say if we have total of 7 elements for eg: {10, 13, 10, 13, 10, 4, 13}. Now if we count total number of ones for LSB in the whole array, we will get 3(for 3 13s, for every other number LSB is 0). Now if we find remainder of the count when divided by 3, we will get the LSB of the desired number. Why? Because every other number appears three times, hence all other ones will appear three times and when taking a remainder will cancel out.
We can do the same thing for all 32 bits :). Below is the code.
int singleNumber(int A[], int n) {
    int num = 0;
    int temp = 0;
    for(int i = 0; i < 32; i++)
    {
        for(int j = 0; j < n; j ++)
        {
            if((A[j] >> i) & 1)
                temp ++;
        }
        temp = temp %3;
        num = num | (temp<<i);
        temp = 0;
    }
    return num;
}


No comments:

Post a Comment