Count pairs from a given array whose sum lies from a given range | C ++ program for the above approach ; Function to count pairs whose sum lies over the range [ L , R ] ; Sort the given array ; Iterate until right > 0 ; Starting index of element whose sum with arr [ right ] >= L ; Ending index of element whose sum with arr [ right ] <= R ; Update the value of end ; Add the count of elements to the variable count ; Return the value of count ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countPairSum ( int arr [ ] , int L , int R , int N ) { sort ( arr , arr + N ) ; int right = N - 1 , count = 0 ; while ( right > 0 ) { auto it1 = lower_bound ( arr , arr + N , L - arr [ right ] ) ; int start = it1 - arr ; auto it2 = upper_bound ( arr , arr + N , R - arr [ right ] ) ; -- it2 ; int end = it2 - arr ; end = min ( end , right - 1 ) ; if ( end - start >= 0 ) { count += ( end - start + 1 ) ; } right -- ; } return count ; } int main ( ) { int arr [ ] = { 5 , 1 , 2 , 4 , 3 } ; int L = 5 , R = 8 ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << countPairSum ( arr , L , R , N ) ; return 0 ; }