Number of subarrays having absolute sum greater than K | Set | Python3 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
from bisect import bisect as upper_bound NEW_LINE maxLen = 30 NEW_LINE def findCnt ( arr , n , k ) : NEW_LINE INDENT ans = 0 NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT arr [ i ] += arr [ i - 1 ] NEW_LINE if ( arr [ i ] > k or arr [ i ] < - 1 * k ) : NEW_LINE INDENT ans += 1 NEW_LINE DEDENT DEDENT if ( arr [ 0 ] > k or arr [ 0 ] < - 1 * k ) : NEW_LINE INDENT ans += 1 NEW_LINE DEDENT arr = sorted ( arr ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT ans += n - upper_bound ( arr , arr [ i ] + k ) NEW_LINE DEDENT return ans NEW_LINE DEDENT arr = [ - 1 , 4 , - 5 , 6 ] NEW_LINE n = len ( arr ) NEW_LINE k = 0 NEW_LINE print ( findCnt ( arr , n , k ) ) NEW_LINE