Ways to choose three points with distance between the most distant points <= L | Returns the number of triplets with the distance between farthest points <= L ; Sort the array ; Find index of element greater than arr [ i ] + L ; Find Number of elements between the ith index and indexGreater since the Numbers are sorted and the elements are distinct from the points btw these indices represent points within range ( a [ i ] + 1 and a [ i ] + L ) both inclusive ; If there are at least two elements in between i and indexGreater find the Number of ways to select two points out of these ; Set of n points on the X axis
function countTripletsLessThanL ( n , L , arr ) { arr . sort ( function ( a , b ) { return a - b } ) ; let ways = 0 ; for ( let i = 0 ; i < n ; i ++ ) { let indexGreater = upper_bound ( arr , 0 , n , arr [ i ] + L ) ; let numberOfElements = indexGreater - ( i + 1 ) ; if ( numberOfElements >= 2 ) { ways += ( numberOfElements * ( numberOfElements - 1 ) / 2 ) ; } } return ways ; } function upper_bound ( a , low , high , element ) { while ( low < high ) { let middle = low + parseInt ( ( high - low ) / 2 , 10 ) ; if ( a [ middle ] > element ) high = middle ; else low = middle + 1 ; } return low ; } let arr = [ 1 , 2 , 3 , 4 ] ; let n = arr . length ; let L = 4 ; let ans = countTripletsLessThanL ( n , L , arr ) ; document . write ( " " + ans ) ;