Find missing number and duplicate elements in an array

Given an limited range array of integers of size n with all its elements between 1 to n with the exception of one element which occur twice and one number which is missing from the list. Find missing number and the duplicate element in linear time and without using any extra memory.

 

For example,

 

Input: arr = [4, 3, 6, 5, 2, 4]

Output: Duplicate and missing elements are 4 and 1 respectively

 

Related Posts: Find two odd occurring element in an array without using any extra space

 


 

We can solve this problem in O(n) time and in O(1) space using XOR operator. We know that if we XOR a number with itself odd number of times the result is number itself, otherwise if we XOR a number even number of times with itself, the result is 0. Also XOR with 0 is always the number itself.


XOR x with 0

x ^ 0 = x
 

XOR x with itself even number of times

x ^ x = 0
x ^ x ^ x ^ x = (x ^ x) ^ (x ^ x) = 0 ^ 0 = 0
 

XOR x with itself odd number of times

(x ^ x ^ x) = (x ^ (x ^ x)) = (x ^ 0) = x
(x ^ x ^ x ^ x ^ x) = (x ^ (x ^ x) ^ (x ^ x)) = (x ^ 0 ^ 0) = x

 

So, if we take XOR of all elements present in the array with every element in the range [1 .. n], even appearing elements will cancel out each other and we are left with XOR of x and y (x ^ y) where x and y is duplicate and missing element. Note that the duplicate element will be XORed 3 times in total and missing element will be XORed 1 times, whereas all others elements will be XORed twice.
 

How to find x and y?


res = (x ^ y)

We know that any set bit in res will be either set in x or y (but not in both as a bit will only set in res when it is set in one number and unset in the other).

The idea is to consider the rightmost set bit in res (or any other set bit) and split the array/range into two lists –

  1. First list contains all elements of the array and numbers in range that have this bit set.
     
  2. Second list contains all elements of the array and numbers in range that have this bit unset.

As rightmost bit is set in one number and unset in the other, we will have duplicate element present in one list and missing number present in the other. Basically we have isolated trait of one number with other so that both x and y will go to different lists.

Now we iterate both lists once more, do XOR on each element of the list and the result will be the duplicate element present in one list and missing number present in the other list (since elements appearing twice will cancel each other).

C++

Download   Run Code

Output:

Duplicate and missing elements are 4 and 1

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
Notify of