educative.io

Educative

Any resource for proof of "We can take any bit which is ‘1’ in n1xn2 and partition all numbers in the given array into two groups based on that bit."

I am having hard trying to understand why it would work?

May be something is obvious and I am not aware?

1 Like

I believe this technique works because we have every number duplicated except the two. So, two different numbers when XORed with each other we get a kind of a mask.

Every 0 bit in this mask denotes that corresponding bits in both numbers are the same, and every 1 bit means the opposite. So we can get any such 1 bit and partition the numbers into two groups.

What does this mean? It means that each number where the corresponding bit is set will go into one group and numbers with an opposite bit will go into the other group. So each group will have duplicate numbers except the one which is unique. In this way, no two same numbers can go into different groups cause this would mean that their corresponding bits are different which would mean that they’re not duplicates.

example:
[2,1,3,2]
1 ^ 3 = 0b10

2 = 0b10
1 = 0b01
3 = 0b11

so when we partition these numbers according to the first set bit in the mask we’ll get [2,2,3] in one group and [1] in the other. So, if we XOR them separately we’ll get 3 for the first one (cuz 2’s zero out each other) and 1 for the second one and there you have it. Hope this will help to clear things up!

1 Like

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.

A good topic to explore to understand why it works is understand Xor, Anding , truth tables. Look at the topic bit masking and bit merging in binary form.

Also try to get answers to basic questions like,

  1. How can you find in a given binary number bit at nth place is 0 or 1?
  2. if the xor sum of two numbers has bit 1 at 2nd(nth) place, what will be the value of each numbers 2nd bit?

These fundamental questions will get you understand foundation very well.