# 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; // 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.”

1. Nice One