Number of anomalies in an array | JavaScript program for 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
function countAnomalies ( a , n , k ) { a . sort ( ) ; let res = 0 ; for ( let i = 0 ; i < n ; i ++ ) { let u = upper_bound ( a , 0 , n , a [ i ] ) ; if ( u < n && a [ u ] - a [ i ] <= k ) continue ; let s = lower_bound ( a , 0 , n , a [ i ] ) ; if ( u - s > 1 ) continue ; if ( s > 0 && a [ s - 1 ] - a [ i ] <= k ) continue ; res ++ ; } return res ; } function lower_bound ( a , low , high , element ) { while ( low < high ) { let middle = low + Math . floor ( ( high - low ) / 2 ) ; if ( element > a [ middle ] ) low = middle + 1 ; else high = middle ; } return low ; } function upper_bound ( a , low , high , element ) { while ( low < high ) { let middle = low + Math . floor ( ( high - low ) / 2 ) ; if ( a [ middle ] > element ) high = middle ; else low = middle + 1 ; } return low ; } let arr = [ 7 , 1 , 8 ] , k = 5 ; let n = arr . length ; document . write ( countAnomalies ( arr , n , k ) ) ;