## Given two integer arrays where one array is duplicate of another array with just 1 element missing. Find the missing element.

We have two integer arrays where one array is duplicate of another array with just 1 element missing. We need to find the missing element. There are 2 algorithms described in this article to solve the problem.

Consider the following example

Input :

```int[] array1 = {5, 2, 4, 6, 7, 9, 22};
int[] array2 = {2, 22, 6, 5, 9, 7};```

Output : Missing Number : 4

Algorithm 1 :
1. Iterate over array1, find sum of all numbers of array1, say result.
2. Iterate over array2 and subtract every element of array2 from result.
3. Print result.

Following is the implementation of the algorithm

```public class FindMissingNumberInDuplicateArrayUsingSum {

public static int getMissingNumberInDuplicateArrayUsingSum(int[] inArray1,
int[] inArray2) throws Exception {

// throws exception when both the input array is NULL
if (inArray1 == null && inArray2 == null) {
throw new Exception("Input is not valid.");
}

// throws exception when one of the input array is NULL and the other array
// has more than one element
if (inArray1 == null && inArray2.length > 1) {
throw new Exception("Input is not valid.");
}
if (inArray2 == null && inArray1.length > 1) {
throw new Exception("Input is not valid.");
}

// get missing number when one of the input array is NULL
int result = getMissingNumberWhenOneArrayIsNull(inArray1, inArray2);
if (result > 0) {
return result;
}

// for all other cases
int len1 = inArray1.length;
int len2 = inArray2.length;
if (Math.abs(len1 - len2) != 1) {
// there should be only one missing number
throw new Exception("Input is not valid.");
}
if (len1 > len2) {
result = findMissingNumberUsingSum(inArray1, inArray2);
} else {
result = findMissingNumberUsingSum(inArray2, inArray1);
}
return result;
}

private static int getMissingNumberWhenOneArrayIsNull(int[] inArray1,
int[] inArray2) throws Exception {
int result = 0;
if (inArray1 == null) {
result = inArray2[0];
} else if (inArray2 == null) {
result = inArray1[0];
}
return result;
}

private static int findMissingNumberUsingSum(int[] array1, int[] array2) {
int result = 0;
for (int i = 0; i < array1.length; i++) {
result += array1[i];
}
for (int i = 0; i < array2.length; i++) {
result -= array2[i];
}
return result;
}

public static void main(String[] args) {
int[] array1 = {5, 2, 4, 6, 7, 9, 22};
int[] array2 = {2, 22, 6, 5, 9, 7};
try {
System.out.println("Missing Number :"
+ getMissingNumberInDuplicateArrayUsingSum(array1, array2));
} catch (Exception e) {
// LOG Exception properly
e.printStackTrace();
}
}
}
```

Algorithm 2 :
1. Initialize result = 0.
2. Iterate over both the input arrays and XOR 'result' with each element of the input arrays.
3. Print result.

Following is the implementation of the algorithm

```public class FindMissingNumberInDuplicateArrayUsingXOR {

public static int getMissingNumberInDuplicateArrayUsingXOR(int[] inArray1,
int[] inArray2) throws Exception {

// throws exception when both the input array is NULL
if (inArray1 == null && inArray2 == null) {
throw new Exception("Input is not valid.");
}

// throws exception when one of the input array is NULL and the other array
// has more than one element
if (inArray1 == null && inArray2.length > 1) {
throw new Exception("Input is not valid.");
}
if (inArray2 == null && inArray1.length > 1) {
throw new Exception("Input is not valid.");
}

// get missing number when one of the input array is NULL
int result = getMissingNumberWhenOneArrayIsNull(inArray1, inArray2);
if (result > 0) {
return result;
}

// for all other cases
int len1 = inArray1.length;
int len2 = inArray2.length;
if (Math.abs(len1 - len2) != 1) {
// there should be only one missing number
throw new Exception("Input is not valid.");
}
if (len1 > len2) {
result = findMissingNumberUsingXOR(inArray1, inArray2);
} else {
result = findMissingNumberUsingXOR(inArray2, inArray1);
}
return result;
}

private static int getMissingNumberWhenOneArrayIsNull(int[] inArray1,
int[] inArray2) throws Exception {
int result = 0;
if (inArray1 == null) {
result = inArray2[0];
} else if (inArray2 == null) {
result = inArray1[0];
}
return result;
}

private static int findMissingNumberUsingXOR(int[] array1, int[] array2) {
int result = array1[0];
for (int i = 1; i < array1.length; i++) {
result = result ^ array1[i];
}
for (int i = 0; i < array2.length; i++) {
result = result ^ array2[i];
}
return result;
}

public static void main(String[] args) {
int[] array1 = {5, 2, 4, 6, 7, 9, 22};
int[] array2 = {2, 22, 6, 5, 9, 7};
try {
System.out.println("Missing Number :"
+ getMissingNumberInDuplicateArrayUsingXOR(array1, array2));
} catch (Exception e) {
// LOG Exception properly
e.printStackTrace();
}
}
}```

core java 12 Algorithm 12