# Accepted code with proper Explaination. Does anyone have a better idea?

• The code makes use of 2 variables.

ones - At any point of time, this variable holds XOR of all the elements which have
appeared "only" once.
twos - At any point of time, this variable holds XOR of all the elements which have
appeared "only" twice.

So if at any point time,

1. A new number appears - It gets XOR'd to the variable "ones".
2. A number gets repeated(appears twice) - It is removed from "ones" and XOR'd to the
variable "twos".
3. A number appears for the third time - It gets removed from both "ones" and "twos".

The final answer we want is the value present in "ones" - coz, it holds the unique element.

So if we explain how steps 1 to 3 happens in the code, we are done.
Before explaining above 3 steps, lets look at last three lines of the code,

All it does is, common 1's between "ones" and "twos" are converted to zero.

For simplicity, in all the below explanations - consider we have got only 4 elements in the array (one unique element and 3 repeated elements - in any order).

## Explanation for step 1

Lets say a new element(x) appears.

CURRENT SITUATION - Both variables - "ones" and "twos" has not recorded "x".

Observe the statement "twos| = ones & x".
Since bit representation of "x" is not present in "ones", AND condition yields nothing. So "twos" does not get bit representation of "x".
But, in next step "ones ^= x" - "ones" ends up adding bits of "x". Thus new element gets recorded in "ones" but not in "twos".

The last 3 lines of code as explained already, converts common 1's b/w "ones" and "twos" to zeros.
Since as of now, only "ones" has "x" and not "twos" - last 3 lines does nothing.

## Explanation for step 2.

Lets say an element(x) appears twice.

CURRENT SITUATION - "ones" has recorded "x" but not "twos".

Now due to the statement, "twos| = ones & x" - "twos" ends up getting bits of x.
But due to the statement, "ones ^ = x" - "ones" removes "x" from its binary representation.

Again, last 3 lines of code does nothing.
So ultimately, "twos" ends up getting bits of "x" and "ones" ends up losing bits of "x".

## Explanation for step 3.

Lets say an element(x) appears for the third time.

CURRENT SITUATION - "ones" does not have bit representation of "x" but "twos" has.

Though "ones & x" does not yield nothing .. "twos" by itself has bit representation of "x". So after this statement, "two" has bit representation of "x".
Due to "ones^=x", after this step, "one" also ends up getting bit representation of "x".

Now last 3 lines of code removes common 1's of "ones" and "twos" - which is the bit representation of "x".
Thus both "ones" and "twos" ends up losing bit representation of "x".

`````` class Solution {
public:
// Let us take the example of {3, 3, 2, 3} to understand this
int singleNumber(int A[], int n) {
int ones=0, twos =0;
for(int i=0; i<n;i++)
{
/* The expression "one & arr[i]" gives the bits that are
there in both 'ones' and new element from arr[].  We
add these bits to 'twos' using bitwise OR

Value of 'twos' will be set as 0, 3, 3 and 1 after 1st,
2nd, 3rd and 4th iterations respectively */

twos= twos|(ones&A[i]);
/* XOR the new bits with previous 'ones' to get all bits
appearing odd number of times

Value of 'ones' will be set as 3, 0, 2 and 3 after 1st,
2nd, 3rd and 4th iterations respectively */
ones=ones^A[i];
/* The common bits are those bits which appear third time
So these bits should not be there in both 'ones' and 'twos'.
common_bit_mask contains all these bits as 0, so that the bits can
be removed from 'ones' and 'twos'

Value of 'common_bit_mask' will be set as 00, 00, 01 and 10
after 1st, 2nd, 3rd and 4th iterations respectively */
/* Remove common bits (the bits that appear third time) from 'ones'

Value of 'ones' will be set as 3, 0, 0 and 2 after 1st,
2nd, 3rd and 4th iterations respectively */
/* Remove common bits (the bits that appear third time) from 'twos'

Value of 'twos' will be set as 0, 3, 1 and 0 after 1st,
2nd, 3rd and 4th itearations respectively */
}
return ones;
}
};``````

• best explanation

• Thank u @diego2 :)

• Hey @Deepalaxmi,

Welcome to DIscuss. Thanks for sharing such thoughtful analysis. Keep up the good work!

• One of the best explanations I've ever met.

• thanks. very nice explanation.

• This post is deleted!

• very clear explanation

• Thank you very much!

• This post is deleted!

• a very nice explanation, i have read it twice. thx

• Very Nice Explanation. Out of all the answers posted for this solution filtered with highest number of votes, this is by far the best explained solution. All the others, despite having more votes are extremely difficult to understand. Play with this solution with a small example like 5,5,5,7 ...ans is 7.

• Thank you very much. This is the best explanation I have ever seen!

• Simple and concise. Thank you.

• great explanation . Thanks

• Excellent Solution

• great explaination!!!! Please can you tell if we can extend it to general solution for eg 4,5... occurrence?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.