Find The Missing Duplicate in a Given Array.

Objec­tive: Given an Integer array. Array contains duplicates of all the numbers in array except one number . Find that number.

Example :

int [] A = { 2,1,3,5,5,3,2,1,6,7,7,8,8};
Output : Missing duplicate is 6


  • Naive solution is use Hash Table complexity – O(n)
  • Better solution – XOR
  • A^A = 0 and A^B^A = B, so if we XOR all the elements, answer will be the missing no
  • If we have only one element, the missing no will be that no



Missing duplicate is 6

Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.

You may also like...

  • anchal dhiman

    Nice One

%d bloggers like this: