Find the element that appears once

Question

Find the element that appears once

Given an array where every element occurs three times, except one element which occurs only once. Find the element that occurs once.

Expected time complexity is O(n) and O(1) extra space.

Examples:

Input: arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 3}

Output: 2

Answer 1

If O(1) space constraint was not there, you could've gone for a hashmap with values being the count of occurrences.

int getUniqueElement(int[] arr)
{
    int ones = 0 ; //At any point of time, this variable holds XOR of all the elements which have appeared "only" once.
    int twos = 0 ; //At any point of time, this variable holds XOR of all the elements which have appeared "only" twice.
    int not_threes ;

    for( int x : arr )
    {
        twos |= ones & x ; //add it to twos if it exists in ones
        ones ^= x ; //if it exists in ones, remove it, otherwise, add it

        // Next 3 lines of code just converts the common 1's between "ones" and "twos" to zero.

        not_threes = ~(ones & twos) ;//if x is in ones and twos, dont add it to Threes.
        ones &= not_threes ;//remove x from ones
        twos &= not_threes ;//remove x from twos
    } 
    return ones;
}

Basically, it makes use of the fact that x^x = 0 and 0^x=x. So all paired elements get XOR'd and vanish leaving the lonely element.

In short :

If a bit is already in ones, add it to twos.

XOR will add this bit to ones if it's not there or remove this bit from ones if it's already there.

If a bit is in both ones and twos, remove it from ones and twos.

When finished, ones contains the bits that only appeared 3*n+1 times, which are the bits for the element that only appeared once.