Missing and repeating number in array

Missing and repeating number in array

Given an array of integers, range from 1 to N, there is one number missing and one number is repeated. Identify missing and repeating number in array. For example:

A = [1,2,2,3,5] Here 4 is missing and 2 is repeated

A = [3,2,1,1,4] Here 5 missing and 1 is repeated.

In posts Find missing number in array and Find repeating number in array, problems to find repeated and missing number, followed same approach. In case of missing number, number was not XORed with itself resulting in answer, while in case of repeating number, number was XORed with itself thrice, resulting in answer.

Now, if we follow approach we did in last two problems, the result will contain XOR of missing and repeating number. How do we segregate these two numbers?
When two numbers are XORed, set bits in result are the bits which are different in  two numbers which are XORed.
For example if we XOR 1 and 3  (001 and 011), result is 010. Only bit set is 2nd as 2nd bit in 001 and 011 is different. Let’s extend this insight. If result is XOR of missing and repeating number, any bit set in result will be different in XORed numbers. If we find one such bit in result, we can safely say that one (missing or repeating) will have this bit set and other will have it as zero.
How to find the first bit which is set in a number? Below is the expression.
log2 (X & ~ (X-1))
  
X = 5 , X-1  = 4 expression result  = 101 & ~(100) = 101 & 011 = 001
log2(001) = 0 hence zeroth bit is set.

X = 4, X-1 = 3 expression result = 100 & ~(011) = 100 & 100 = 100
log2(100) = 2, hence 2nd bit is set.
Now, we know which bit differs in missing and repeated number. We will segregate our input space based on this bit. All numbers which have this bit set will form one group and all numbers which have this bit as reset, will form second group.
So again go back to array, from 1 to N and 0 to size, XOR numbers in two buckets, one buckets contains XOR result of XORing all numbers with given bit set and other bucket contains XOR result of XORing all numbers with given bit reset.

Algorithm for missing and repeating number

1. XOR all numbers in array, call it actualXOR
2. XOR all numbers from 1 to N, call it expectedXOR
3. XOR actualXOR and expectedXOR. Call it finalXOR.
4. Find right most bit set in finalXOR, let it be kth bit.
5. Now XOR all numbers in array whose kth bit is set. Be it X
6. XOR all numbers in array whose kth bit is reset. Be it Y.
7. XOR all numbers from 1 to N with X which have kth bit set.
8. XOR all numbers from 1 to N with Y whose Kth bit is reset.
9. X and Y are missing and repeating numbers

Missing and repeating number implementation

Complexity of XOR method to find missing and repeating number in array is O(n).
Please share if you have suggestion or if something is missing. If you want to contribute, please refer : Publish