# 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.
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;
}

```

### One Thought on “Find the Element that Appears Once”

1. Shivani Tomar on May 31, 2017 at 4:24 pm said:

I don’t understand the logic. will anyone explain what is the logic behind this question