- 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.
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 :
X | Y | Output |
---|---|---|
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
- 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 |