Number of subarrays having absolute sum greater than K | Set | Java implementation of the approach ; Function to find required value ; Variable to store final answer ; Loop to find prefix - sum ; Sorting prefix - sum array ; Loop to find upper_bound for each element ; Returning final answer ; Driver code ; Function to find required value
import java . util . * ; class GFG { static int maxLen = 30 ; static int findCnt ( int arr [ ] , int n , int k ) { int ans = 0 ; for ( int i = 1 ; i < n ; i ++ ) { arr [ i ] += arr [ i - 1 ] ; if ( arr [ i ] > k arr [ i ] < - 1 * k ) ans ++ ; } if ( arr [ 0 ] > k arr [ 0 ] < - 1 * k ) ans ++ ; Arrays . sort ( arr ) ; for ( int i = 0 ; i < n ; i ++ ) ans += n - upper_bound ( arr , 0 , n , arr [ i ] + k ) ; return ans ; } 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 [ ] = { - 1 , 4 , - 5 , 6 } ; int n = arr . length ; int k = 0 ; System . out . println ( findCnt ( arr , n , k ) ) ; } }