educative.io

Can the solution be visualized better?

Courses
,
#1

Finding it difficult to visualize based on following algorithm.

1. Taking XOR of all numbers in the given array will give us XOR of num1 and num2, 
calling this XOR as n1xn2.

2. Find any bit which is set in n1xn2. We can take the rightmost bit which is ‘1’. 
Let’s call this rightmostSetBit.

3. Iterate through all numbers of the input array to partition them into two groups 
based on rightmostSetBit. Take XOR of all numbers in both the groups separately. 
Both these XORs are our required numbers.

Anyone else too?

#2

The most straight forward reason for this is every number (except 2) will XOR out to 0.
Now visualize all the numbers in binary representation one below the other.
The ones XORing out to 0 MUST HAVE identical bit masks (of course so, because all, except 2 are duplicates and the duplicates will have identical bit masks, because the values are identical). So, the only values contributing to the final non-zero XOR value are the 2 non-repeating numbers.
So, basically XORing only those 2 non-repeating numbers and XORing all the numbers is effectively same.
And the NON-ZERO final XOR gives in a very important clue. The clue that it is NON-ZERO. And that means, because of XOR’s mutually exclusive properties, the two non-repeating numbers must have AT LEAST one bit different. Since that bit has contributed to final NON-ZERO XOR value, all the rest of the numbers HAVE TO HAVE CANCELLED EACH OTHER. There’s absolutely no way that bit is staying NON-ZERO, otherwise. So, you can trust only one (any one) set bit in the final XOR value. That is bit is sure to be set odd number of times in the entire set (because then only it can be exclusive and hence set in the final XOR value), AND, IMPORTANTLY, it HAS TO be set ON in one number, and OFF in the other. So, that bit can help split the entire set into 2 halves, effectively reducing the problem to finding only one non-repeating number, but this time, in 2 sets from the original set. Think about it. Just pay close attention to the XOR’s properties. It would start making sense.

2 Likes
#3

Understand XOR truth table

1 1 0
1 0 1
0 1 1
0 0 0

  1. Once you do Xor of all the numbers in the given array - except 2 nos , all numbers have 2 entries. therefore they cancel out each other based on Xor operation. Example 9 Xor 9 = 0 , Xor properties , N1 XOR N2 XOR N3 … XOR Nn is same as N1 XOR Nn XOR N2 XOR N5… , which means ultimately the final value of N1xN2 is not zero but represent the xor sum of 2 numbers which has only one entry each , all duplicates (double) entry numbers cancels out each other.

  2. If you look at truth table of XOR, For any Xor sum to have bit as 1, it needs 0, i.e 1 xor 0 or 0 xor 1. Now you have ask question to yourself, if I find set bit or bit with value 1 in n1xn2, then you can be sure that this particular bit has value 0 in one number and 1 in another number because in n1xn2, this particular bit is 1.
    Another question you can ask yourself, how can I find, which bit is set ?, then again back to basics of AND properties, you can find if a given number has bit set(1) or not by simply ANDing it as only 1 & 1 gives answer as 1, therefore , you start with rightmost bit , if you find value of n1xn2 & righmostBit as non-zero , that means you have found the bit which has value one in n1xn2 otherwise, it will result in zero.

So basically you start with 0000001 , and keep shifting until you get non-zero answer , 00000010 , …0000100, => look at this binary bit this is what you righmostsetBit variable hold in binary form and you are Anding it with n1xn2 , so that you get exactly which bit is the rightmostSetBit.

  1. In point 1, as mentioned, it takes 0 and 1 to Xor to produce resultant 1 . We can divide the given input array based on all numbers which has 0 in that particular bit place, and ultimately all duplicated will fall into same group and 1 number , and other group with other number. In this way, if you xor within each of the group, finally you will be left with num1 from each group and num2 from other group.