Triplets in array with absolute difference less than k | CPP program to count triplets with difference less than k . ; Return the lower bound i . e smallest index of element having value greater or equal to value ; Return the number of triplet indices satisfies the three constraints ; sort the array ; for each element from index 2 to n - 1. ; finding the lower bound of arr [ i ] - k . ; If there are at least two elements between lower bound and current element . ; increment the count by lb - i C 2. ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int binary_lower ( int value , int arr [ ] , int n ) { int start = 0 ; int end = n - 1 ; int ans = -1 ; int mid ; while ( start <= end ) { mid = ( start + end ) / 2 ; if ( arr [ mid ] >= value ) { end = mid - 1 ; ans = mid ; } else { start = mid + 1 ; } } return ans ; } int countTriplet ( int arr [ ] , int n , int k ) { int count = 0 ; sort ( arr , arr + n ) ; for ( int i = 2 ; i < n ; i ++ ) { int cur = binary_lower ( arr [ i ] - k , arr , n ) ; if ( cur <= i - 2 ) { count += ( ( i - cur ) * ( i - cur - 1 ) ) / 2 ; } } return count ; } int main ( ) { int arr [ ] = { 1 , 1 , 2 , 2 , 3 } ; int k = 1 ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << countTriplet ( arr , n , k ) << endl ; return 0 ; }