Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Find The Missing Duplicate in a Given Array.

Objec­tive: - Given an Inte­ger array. Array con­tains dupli­cates of all the num­bers in array except one num­ber . Find that number.

Exam­ple :

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


Appraoch:

  • Naive solu­tion is use Hash Table ..space com­plex­ity — O(n)
  • Bet­ter solu­tion - XOR
  • A^A = 0 and A^B^A = B, so if we XOR all the ele­ments, answer will be the miss­ing no
  • If we have only one ele­ment, the miss­ing no will be that no

Code:


Out­put:

Missing duplicate is 6

You may also like...

  • anchal dhi­man

    Nice One