Given an unsorted array of size N of positive integers. One number ‘A’ from set {1, 2, …N} is missing and one number ‘B’ occurs twice in the array. Find these two numbers.
Let’s try to solve this problem for this example [1, 2, 4, 4, 5]
if nothing is missing and repeating then the set look like [1, 2, 3, 4, 5]
after merging both resulting [1, 2, 4, 4, 5, 1, 2, 3, 4, 5]
here you can observe everyone is repeating even times except numbers that we have to find.
next, we calculate the bitwise-xor of [1, 2, 4, 4, 5, 1, 2, 3, 4, 5]
contribution of numbers occurring even times, in bitwise xor is zero as they cancel each other.
so only numbers contribute in bitwise-xor. => [3, 4]
3 = 011 , 4 = 100 , bitwise-xor of 3 and 4 = 111 = 7 (decimal)
from the xor table, you notice if the output of xor op is 1 then it come from either first or second.
lets try to find candidates for repeating and missing calling A and B respectively, for this, we can use resultant xor value (7)
if any bit 7 is set then it comes from either A or B both not both of them as the same bits cancel each other.
I pick the first set bit from 7 (you can take any set bit)
I am assuming here set bit come from B.
criteria for B : numbers having first bit is 1.
numbers from a given array having first set bit : [ 1, 5]
as candidates Available for B : [1, 5]
But B can be anyone from [1, 2, 3, 4, 5]
so an actual set of candidates = [ 1, 3 , 5]
here you can see candidate 3 is missing.
you can get repeating number 4 by applying bitwise operation on 3 and 7.
here you have to check either calculated B is missing or repeating using Linear Search.
Time Complexity : O(N)
Happy Coding
