text: Find the missing number in unordered Arithmetic Progression | C ++ 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 ; Driver Code ; Given array arr [ ] ; Function Call
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; int findMissing ( int arr [ ] , int left , int right , int diff ) { if ( right <= left ) return INT_MAX ; int mid = left + ( right - left ) / 2 ; if ( arr [ mid + 1 ] - arr [ mid ] != diff ) return ( arr [ mid ] + diff ) ; if ( mid > 0 && arr [ mid ] - arr [ mid - 1 ] != diff ) return ( arr [ mid - 1 ] + diff ) ; if ( arr [ mid ] == arr [ 0 ] + mid * diff ) return findMissing ( arr , mid + 1 , right , diff ) ; return findMissing ( arr , left , mid - 1 , diff ) ; } int missingElement ( int arr [ ] , int n ) { sort ( arr , arr + n ) ; int diff = ( arr [ n - 1 ] - arr [ 0 ] ) / n ; return findMissing ( arr , 0 , n - 1 , diff ) ; } int main ( ) { int arr [ ] = { 2 , 8 , 6 , 10 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << missingElement ( arr , n ) ; return 0 ; }