Count triplets with sum smaller than a given value | Python3 program to count triplets with sum smaller than a given value ; Sort input array ; Initialize result ; Every iteration of loop counts triplet with first element as arr [ i ] . ; 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 more or equal , move right corner to look for smaller values ; Else move left corner ; This is important . For current i and j , there can be total k - j third elements . ; Driver program
def countTriplets ( arr , n , sum ) : NEW_LINE INDENT arr . sort ( ) NEW_LINE ans = 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 if ( arr [ i ] + arr [ j ] + arr [ k ] >= sum ) : NEW_LINE INDENT k = k - 1 NEW_LINE DEDENT else : NEW_LINE INDENT ans += ( k - j ) NEW_LINE j = j + 1 NEW_LINE DEDENT DEDENT DEDENT return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 5 , 1 , 3 , 4 , 7 ] NEW_LINE n = len ( arr ) NEW_LINE sum = 12 NEW_LINE print ( countTriplets ( arr , n , sum ) ) NEW_LINE DEDENT