Count number of triplets in an array having sum in the range [ a , b ] | Function to find count of triplets having sum less than or equal to val . ; sort the input array . ; Initialize result ; to store sum ; Fix the first element ; Initialize other two elements as corner elements of subarray arr [ j + 1. . k ] ; Use Meet in the Middle concept . ; If sum of current triplet is greater , then to reduce it decrease k . ; If sum is less than or equal to given value , then add possible triplets ( k - j ) to result . ; Function to return count of triplets having sum in range [ a , b ] . ; to store count of triplets . ; Find count of triplets having sum less than or equal to b and subtract count of triplets having sum less than or equal to a - 1. ; Driver code
def countTripletsLessThan ( arr , n , val ) : NEW_LINE INDENT arr . sort ( ) NEW_LINE ans = 0 NEW_LINE j = 0 ; k = 0 NEW_LINE sum = 0 NEW_LINE for i in range ( 0 , n - 2 ) : NEW_LINE INDENT j = i + 1 NEW_LINE k = n - 1 NEW_LINE while j != k : NEW_LINE INDENT sum = arr [ i ] + arr [ j ] + arr [ k ] NEW_LINE if sum > val : NEW_LINE INDENT k -= 1 NEW_LINE DEDENT else : NEW_LINE INDENT ans += ( k - j ) NEW_LINE j += 1 NEW_LINE DEDENT DEDENT DEDENT return ans NEW_LINE DEDENT def countTriplets ( arr , n , a , b ) : NEW_LINE INDENT res = 0 NEW_LINE res = ( countTripletsLessThan ( arr , n , b ) - countTripletsLessThan ( arr , n , a - 1 ) ) NEW_LINE return res NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 2 , 7 , 5 , 3 , 8 , 4 , 1 , 9 ] NEW_LINE n = len ( arr ) NEW_LINE a = 8 ; b = 16 NEW_LINE print ( countTriplets ( arr , n , a , b ) ) NEW_LINE DEDENT