Repeating and Missing Number in Array

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)

xor operation

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