Find the element that appeared once in the array
Problem Description: 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
People find it difficult to understand bit manipulations on numbers which is why this problem looks tricky.
Let's start with what we know, we have an array in which one element is unique and remaining are repeated twice. So we do XOR for all elements in the array and all the numbers which are repeated twice will be neutralized and the value remaining in the variable is our answer.
So we should note one thing here, that is doing XOR for the same element will kill the element from the bucket.
But if we do XOR operation for all the elements in the array, we will end up with the resultant variable containing bits that are contributed from every element in the array, since all elements are repeated odd number of times
Now the approach is -
We have two variables
1. Twice repeated elements container — This should contain numbers which appeared twice at any point of time
2. All element container-This basically contain all the numbers (odd number of times repeated elements)Now if you take set bits from both the containers, i.e. if you do AND operation on both containers the resultant number will be the number in which the set bit positions are of numbers that are repeated thrice. Because first container contains twice repeated elements and by doing AND operation with second container, it confirms the elements are thrice repeated
So after every iteration we get these set bits from every container and remove them in ALL ELEMENT CONTAINER. At the end of the day, after all the iterations we will have the element that occured only once because we are removing elements that occurred thrice with the help of other container which holds the elements which occurred twice.
Let us go through the small piece of code which does that:
remember that XOR operation is commutative and associative, so no matter in which order you do it, it works
for( int i=0; i< n; i++ ){
# the below line says store current element only if that had occured before, which means this is second occurence of the element# this has to be done before next line of code because if two same numbers are present contigously you will not know about them because XOR removes them in that container before you store in this containerelements_appeared_twice = elements_appeared_twice | (all_element_container & arr[i]);# the below line does XOR for every elementall_element_container = all_element_container ^ arr[i];# This is crucial, now you will have sets bits of elements that are appeared thrice, by doing negation you will have zeroes in that positions which belong to elements that appeared thrice.common_bit_mask= ~(all_element_container & elements_appeared_twice);# Now you do AND operation with both containers it unsets set bit positions of elements that appeared thriceall_element_container &= common_bit_mask;elements_appeared_twice &= common_bit_mask;}
resultant_number = all_element_container
return resultant_number
I am leaving debugging session to yourself, but I would suggest using pen and paper and go through every step if you are not sure about this.
Go through my other writings if you are interested. Happy Coding :)
