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
import java . util . * ; class GFG { static int countAnomalies ( int a [ ] , int n , int k ) { Arrays . sort ( a ) ; int res = 0 ; for ( int i = 0 ; i < n ; i ++ ) { int u = upper_bound ( a , 0 , n , a [ i ] ) ; if ( u < n && a [ u ] - a [ i ] <= k ) continue ; int 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 ; } static int lower_bound ( int [ ] a , int low , int high , int element ) { while ( low < high ) { int middle = low + ( high - low ) / 2 ; if ( element > a [ middle ] ) low = middle + 1 ; else high = middle ; } return low ; } static int upper_bound ( int [ ] a , int low , int high , int element ) { while ( low < high ) { int middle = low + ( high - low ) / 2 ; if ( a [ middle ] > element ) high = middle ; else low = middle + 1 ; } return low ; } public static void main ( String [ ] args ) { int arr [ ] = { 7 , 1 , 8 } , k = 5 ; int n = arr . length ; System . out . print ( countAnomalies ( arr , n , k ) ) ; } }