Ways to choose three points with distance between the most distant points <= L | Java program to count ways to choose triplets such that the distance between the farthest 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 ; Driver Code ; set of n points on the X axis
import java . util . * ; class GFG { static int countTripletsLessThanL ( int n , int L , int [ ] arr ) { Arrays . sort ( arr ) ; int ways = 0 ; for ( int i = 0 ; i < n ; i ++ ) { int indexGreater = upper_bound ( arr , 0 , n , arr [ i ] + L ) ; int numberOfElements = indexGreater - ( i + 1 ) ; if ( numberOfElements >= 2 ) { ways += ( numberOfElements * ( numberOfElements - 1 ) / 2 ) ; } } return ways ; } static int upper_bound ( int [ ] a , int low , int high , int element ) { while ( low < high ) { int middle = low + ( high - low ) / 2 ; if ( a [ middle ] > element ) high = middle ; else low = middle + 1 ; } return low ; } public static void main ( String [ ] args ) { int arr [ ] = { 1 , 2 , 3 , 4 } ; int n = arr . length ; int L = 4 ; int ans = countTripletsLessThanL ( n , L , arr ) ; System . out . println ( " Total ▁ Number ▁ of ▁ ways ▁ = ▁ " + ans ) ; } }