Advertisement
imashutosh51

Count pairs in a sorted array whose sum is less than x

Aug 10th, 2022 (edited)
42
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.43 KB | None | 0 0
  1. //first approach is brute force
  2. int pairs_count(int arr[],int n,int k){
  3.     int l = 0, r = n-1,res= 0;
  4.     while (l < r){
  5.         if (arr[l] + arr[r] < k){    // If current left and current right have sum smaller than x,
  6.             res += (r - l);          // the all elements from l+1 to r form a pair with current l.
  7.             l++;
  8.         }
  9.         else    // Move to smaller value
  10.             r--;
  11.     }
  12.     return res;
  13. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement