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


Appraoch:

  • Naive solution is use Hash Table ..space 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

Code:


Output:

Missing duplicate is 6

1 Response

  1. anchal dhiman says:

    Nice One

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: