Find lost element from a duplicated array | Java program to find missing element from same arrays ( except one missing element ) ; Function to find missing element based on binary search approach . arr1 [ ] is of larger size and N is size of it . arr1 [ ] and arr2 [ ] are assumed to be in same order . ; special case , for only element which is missing in second array ; special case , for first element missing ; Initialize current corner points ; loop until lo < hi ; If element at mid indices are equal then go to right subarray ; if lo , hi becomes contiguous , break ; missing element will be at hi index of bigger array ; This function mainly does basic error checking and calls findMissingUtil ; Driver Code
import java . io . * ; class MissingNumber { int findMissingUtil ( int arr1 [ ] , int arr2 [ ] , int N ) { if ( N == 1 ) return arr1 [ 0 ] ; if ( arr1 [ 0 ] != arr2 [ 0 ] ) return arr1 [ 0 ] ; int lo = 0 , hi = N - 1 ; while ( lo < hi ) { int mid = ( lo + hi ) / 2 ; if ( arr1 [ mid ] == arr2 [ mid ] ) lo = mid ; else hi = mid ; if ( lo == hi - 1 ) break ; } return arr1 [ hi ] ; } void findMissing ( int arr1 [ ] , int arr2 [ ] , int M , int N ) { if ( N == M - 1 ) System . out . println ( " Missing ▁ Element ▁ is ▁ " + findMissingUtil ( arr1 , arr2 , M ) + "NEW_LINE"); else if ( M == N - 1 ) System . out . println ( " Missing ▁ Element ▁ is ▁ " + findMissingUtil ( arr2 , arr1 , N ) + "NEW_LINE"); else System . out . println ( " Invalid ▁ Input " ) ; } public static void main ( String args [ ] ) { MissingNumber obj = new MissingNumber ( ) ; int arr1 [ ] = { 1 , 4 , 5 , 7 , 9 } ; int arr2 [ ] = { 4 , 5 , 7 , 9 } ; int M = arr1 . length ; int N = arr2 . length ; obj . findMissing ( arr1 , arr2 , M , N ) ; } }