Find lost element from a duplicated array | 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
def findMissingUtil ( arr1 , arr2 , N ) : NEW_LINE INDENT if N == 1 : NEW_LINE INDENT return arr1 [ 0 ] ; NEW_LINE DEDENT if arr1 [ 0 ] != arr2 [ 0 ] : NEW_LINE INDENT return arr1 [ 0 ] NEW_LINE DEDENT lo = 0 NEW_LINE hi = N - 1 NEW_LINE while ( lo < hi ) : NEW_LINE INDENT mid = ( lo + hi ) / 2 NEW_LINE if arr1 [ mid ] == arr2 [ mid ] : NEW_LINE INDENT lo = mid NEW_LINE DEDENT else : NEW_LINE INDENT hi = mid NEW_LINE DEDENT if lo == hi - 1 : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT return arr1 [ hi ] NEW_LINE DEDENT def findMissing ( arr1 , arr2 , M , N ) : NEW_LINE INDENT if N == M - 1 : NEW_LINE INDENT print ( " Missing ▁ Element ▁ is " , findMissingUtil ( arr1 , arr2 , M ) ) NEW_LINE DEDENT elif M == N - 1 : NEW_LINE INDENT print ( " Missing ▁ Element ▁ is " , findMissingUtil ( arr2 , arr1 , N ) ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " Invalid ▁ Input " ) NEW_LINE DEDENT DEDENT arr1 = [ 1 , 4 , 5 , 7 , 9 ] NEW_LINE arr2 = [ 4 , 5 , 7 , 9 ] NEW_LINE M = len ( arr1 ) NEW_LINE N = len ( arr2 ) NEW_LINE findMissing ( arr1 , arr2 , M , N ) NEW_LINE