Number of anomalies in an array |  ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countAnomalies ( int a [ ] , int n , int k ) { sort ( a , a + n ) ; int res = 0 ; for ( int i = 0 ; i < n ; i ++ ) { int * u = upper_bound ( a , a + n , a [ i ] ) ; if ( u != a + n && ( ( * u ) - a [ i ] ) <= k ) continue ; int * s = lower_bound ( a , a + n , a [ i ] ) ; if ( u - s > 1 ) continue ; if ( s != a && ( * ( s - 1 ) - a [ i ] ) <= k ) continue ; res ++ ; } return res ; } int main ( ) { int arr [ ] = { 7 , 1 , 8 } , k = 5 ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << countAnomalies ( arr , n , k ) ; return 0 ; }