Find the missing number in unordered Arithmetic Progression | Python3 program for the above approach ; Function to find the missing element ; Fix left and right boundary for binary search ; Find index of middle element ; Check if the element just after the middle element is missing ; Check if the element just before mid is missing ; Check if the elements till mid follow the AP , then recur for right half ; Else recur for left half ; Function to find the missing element in AP series ; Sort the array arr [ ] ; Calculate Common Difference ; Binary search for the missing ; Given array arr [ ] ; Function call
import sys NEW_LINE def findMissing ( arr , left , right , diff ) : NEW_LINE INDENT if ( right <= left ) : NEW_LINE INDENT return sys . maxsize NEW_LINE DEDENT mid = left + ( right - left ) // 2 NEW_LINE if ( arr [ mid + 1 ] - arr [ mid ] != diff ) : NEW_LINE INDENT return ( arr [ mid ] + diff ) NEW_LINE DEDENT if ( mid > 0 and arr [ mid ] - arr [ mid - 1 ] != diff ) : NEW_LINE INDENT return ( arr [ mid - 1 ] + diff ) NEW_LINE DEDENT if ( arr [ mid ] == arr [ 0 ] + mid * diff ) : NEW_LINE INDENT return findMissing ( arr , mid + 1 , right , diff ) NEW_LINE DEDENT return findMissing ( arr , left , mid - 1 , diff ) NEW_LINE DEDENT def missingElement ( arr , n ) : NEW_LINE INDENT arr . sort ( ) NEW_LINE diff = ( arr [ n - 1 ] - arr [ 0 ] ) // n NEW_LINE return findMissing ( arr , 0 , n - 1 , diff ) NEW_LINE DEDENT arr = [ 2 , 8 , 6 , 10 ] NEW_LINE n = len ( arr ) NEW_LINE print ( missingElement ( arr , n ) ) NEW_LINE