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.
When two numbers are XORed, set bits in result are the bits which are different in two numbers which are XORed.
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.
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