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:

public class MissingDuplicate {
// naive solution is use Hash Table ..space complexity – O(n)
// better solutiion – XOR
// A^A = 0 and A^B^A = B, so if we XOR all the elements, answer will be the
// missing no
public int find(int[] A) {
int miss = A[0]; // if we have only one element, the missing no will be
// that no
for (int i = 1; i < A.length; i++) {
miss = miss ^ A[i];
}
return miss;
}
public static void main(String[] args) {
int[] A = { 2, 1, 3, 5, 5, 3, 2, 1, 6, 7, 7, 8, 8 };
MissingDuplicate i = new MissingDuplicate();
System.out.println("Missing duplicate is " + i.find(A));
}
}


Output:

Missing duplicate is 6

1 thought on “Find The Missing Duplicate in a Given Array.”

Leave a Comment

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