Number of subarrays having absolute sum greater than K | Set | Javascript implementation of the above 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
var maxLen = 30 ; function upper_bound ( a , low , high , element ) { while ( low < high ) { var middle = low + parseInt ( ( high - low ) / 2 ) ; if ( a [ middle ] > element ) high = middle ; else low = middle + 1 ; } return low ; } function findCnt ( arr , n , k ) { var ans = 0 ; for ( var 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 ++ ; arr . sort ( ( a , b ) => a - b ) for ( var i = 0 ; i < n ; i ++ ) ans += ( n - upper_bound ( arr , 0 , n , arr [ i ] + k ) ) ; return ans ; } var arr = [ - 1 , 4 , - 5 , 6 ] ; var n = arr . length ; var k = 0 ; document . write ( findCnt ( arr , n , k ) ) ;