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
< ? php function countTripletsLessThan ( $ arr , $ n , $ val ) { sort ( $ arr ) ; $ ans = 0 ; $ sum ; for ( $ i = 0 ; $ i < $ n - 2 ; $ i ++ ) { $ j = $ i + 1 ; $ k = $ n - 1 ; while ( $ j != $ k ) { $ sum = $ arr [ $ i ] + $ arr [ $ j ] + $ arr [ $ k ] ; if ( $ sum > $ val ) $ k -- ; else { $ ans += ( $ k - $ j ) ; $ j ++ ; } } } return $ ans ; } function countTriplets ( $ arr , $ n , $ a , $ b ) { $ res ; $ res = countTripletsLessThan ( $ arr , $ n , $ b ) - countTripletsLessThan ( $ arr , $ n , $ a - 1 ) ; return $ res ; } $ arr = array ( 2 , 7 , 5 , 3 , 8 , 4 , 1 , 9 ) ; $ n = sizeof ( $ arr ) ; $ a = 8 ; $ b = 16 ; echo countTriplets ( $ arr , $ n , $ a , $ b ) , " " ; ? >