Advertisement
imashutosh51

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

Aug 10th, 2022 (edited)
49
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.48 KB | None | 0 0
  1. //first approach is brute force
  2. class Solution:
  3.     #Complete the below function
  4.     def countPairs(self, arr, target):
  5.         arr=sorted(arr)
  6.         ans=0
  7.         i=0
  8.         j=len(arr)-1
  9.         while i<j:
  10.             if arr[i]+arr[j]>=target:
  11.                 j-=1
  12.             else:
  13.                 ans+= (j-i)
  14.                 i+=1
  15.         return ans
  16.  
  17. // If current left and current right have sum smaller than x,
  18. // the all elements from l+1 to r form a pair with current l.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement