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

FOLLOW US ON LinkedIn



Explore Tutu'rself