Number of anomalies in an array | Python3 program to implement the above approach ; Sort the array so that we can apply binary search . ; One by one check every element if it is anomaly or not using binary search . ; If arr [ i ] is not largest element and element just greater than it is within k , then return False . ; If there are more than one occurrences of arr [ i ] , return False . ; If arr [ i ] is not smallest element and just smaller element is not k distance away ; Driver code
def countAnomalies ( a , n , k ) : NEW_LINE INDENT a = sorted ( a ) ; NEW_LINE res = 0 ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT u = upper_bound ( a , 0 , n , a [ i ] ) ; NEW_LINE if ( u < n and a [ u ] - a [ i ] <= k ) : NEW_LINE INDENT continue ; NEW_LINE DEDENT s = lower_bound ( a , 0 , n , a [ i ] ) ; NEW_LINE if ( u - s > 1 ) : NEW_LINE INDENT continue ; NEW_LINE DEDENT if ( s > 0 and a [ s - 1 ] - a [ i ] <= k ) : NEW_LINE INDENT continue ; NEW_LINE DEDENT res += 1 ; NEW_LINE DEDENT return res ; NEW_LINE DEDENT def lower_bound ( a , low , high , element ) : NEW_LINE INDENT while ( low < high ) : NEW_LINE INDENT middle = int ( low + int ( high - low ) / 2 ) ; NEW_LINE if ( element > a [ middle ] ) : NEW_LINE INDENT low = middle + 1 ; NEW_LINE DEDENT else : NEW_LINE INDENT high = middle ; NEW_LINE DEDENT DEDENT return low ; NEW_LINE DEDENT def upper_bound ( a , low , high , element ) : NEW_LINE INDENT while ( low < high ) : NEW_LINE INDENT middle = int ( low + ( high - low ) / 2 ) ; NEW_LINE if ( a [ middle ] > element ) : NEW_LINE INDENT high = middle ; NEW_LINE DEDENT else : NEW_LINE INDENT low = middle + 1 ; NEW_LINE DEDENT DEDENT return low ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 7 , 1 , 8 ] NEW_LINE k = 5 ; NEW_LINE n = len ( arr ) ; NEW_LINE print ( countAnomalies ( arr , n , k ) ) ; NEW_LINE DEDENT