Find missing number or element from duplicated array in java

• Given two arrays, one array is almost duplicate array of another array.
  • Arrays  are duplicated except one element.
  • e.g. array1[] = { 1, 2, 3, 4, 5 } & array2[] = { 1, 2, 4, 5 };
  • array2 does not contain element 3.
• We would like to find missing elements from duplicated arrays.
• We have discussed similar problems.
  • Find a number occurring odd number of times in array.
  • Find a missing number in an array.

Examples – find missing number from duplicated arrays in java

Example 1 – find missing element from two input arrays

• Given two arrays  array1[] = { 1, 2, 3, 4, 5 } & array2[] = { 1, 2, 4, 5 }
• Missing element in array2 is 3

Example 2 -find missing element from two input arrays

• Given two arrays  array1[] = {  10, 20, 30, 40} & array2[] = { 20, 30, 40 }
• Missing element in array2 is 10

Algorithm –  find missing element from duplicated arrays in java

• We will use the properties of XOR gate.
• Truth table of “Exclusive-OR” or XOR gate is :

• Let us apply XOR gate properties of Example 1.
  • array1 = { 1, 2, 3, 4, 5 } &  array2 = { 1, 2, 4, 5 }
• XOR of array1 is = 1 ^ 2 ^ 3 ^ 4 ^  5
  • missingNumber = 1 ^ 2 ^ 3 ^ 4 ^  5
• XOR of array1 & array2 = (1 ^ 2 ^ 3 ^ 4 ^  5)  ^ (1 ^ 2 ^ 4 ^  5 )
  • missingNumber = (1 ^ 2 ^ 3 ^ 4 ^  5)  ^ (1 ^ 2 ^ 4 ^  5 )
• missingNumber = (1 ^ 1) ^ (2 ^ 2) ^  3 ^ (4 ^ 4) ^ (5^ 5)
• missingNumber = 0 ^ 0 ^  3 ^ 0 ^ 0
• missingNumber = 3.

Program – find missing element from duplicated arrays in java

package org.learn.arrays;

import java.util.Arrays;

public class MissingNumberDuplicatedArray {

	private static int missingNumber(int[] arr1, int arr2[]) {

		int missingNumber = arr1[0];
		for (int index = 1; index < arr1.length; index++) {
			missingNumber ^= arr1[index];
		}

		for (int index = 0; index < arr2.length; index++) {
			missingNumber ^= arr2[index];
		}
		return missingNumber;
	}

	public static void main(String[] args) {

		int array1[] = { 1, 2, 3, 4, 5 };
		int array2[] = { 1, 2, 4, 5 };

		String sArr1 = Arrays.toString(array1);
		String sArr2 = Arrays.toString(array2);

		System.out.printf("1. Missing number in array1 & array2 is:", sArr1, sArr2);
		int missingNumber = missingNumber(array1, array2);
		System.out.printf(" %d", missingNumber);

		array1 = new int[] { 10, 20, 30, 40 };
		array2 = new int[] { 20, 30, 40 };

		sArr1 = Arrays.toString(array1);
		sArr2 = Arrays.toString(array2);

		System.out.printf("\n2. Missing number in array1 & array2 is:", sArr1, sArr2);
		missingNumber = missingNumber(array1, array2);
		System.out.printf(" %d", missingNumber);

	}
}

Output – find missing element from duplicated arrays in java

1. Missing number in array1 & array2 is: 3
2. Missing number in array1 & array2 is: 10