Find lost element from a duplicated array | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; 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 ) cout << " Missing ▁ Element ▁ is ▁ " << findMissingUtil ( arr1 , arr2 , M ) << endl ; else if ( M == N - 1 ) cout << " Missing ▁ Element ▁ is ▁ " << findMissingUtil ( arr2 , arr1 , N ) << endl ; else cout << " Invalid ▁ Input " ; } int main ( ) { int arr1 [ ] = { 1 , 4 , 5 , 7 , 9 } ; int arr2 [ ] = { 4 , 5 , 7 , 9 } ; int M = sizeof ( arr1 ) / sizeof ( int ) ; int N = sizeof ( arr2 ) / sizeof ( int ) ; findMissing ( arr1 , arr2 , M , N ) ; return 0 ; }