Find the Element that Appears Once

Problem: 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[] = {10, 1, 10, 3, 10, 1, 1, 2, 3, 3}
Output: 2

Solution:

If O(1) space constraint was not there, we could’ve gone for a hashmap with values being the count of occurrences. But since there is space constraint we can go for bitwise operations.

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.
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.

int getUniqueElement(int[] arr)
{
    //this variable holds XOR of all the elements which have appeared "only" once.
    int ones = 0 ; 
    //this variable holds XOR of all the elements which have appeared "only" twice.
    int twos = 0 ; 
    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, otherwise, add it

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

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


Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation