Iam_Sandeep

Pairs with specific difference

May 5th, 2022 (edited)
232
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.89 KB | None | 0 0
  1. class Solution:
  2.     def maxSumPairWithDifferenceLessThanK(self, arr, n, k):
  3.         '''
  4.        We are sorting in decreasing order because we need to findout
  5.        maxpair sum so we will try to pair maxnumber with 2nd max or 3rd max like that
  6.        '''
  7.         arr.sort(reverse=True)
  8.         i,j=0,1
  9.         ans=0
  10.         while i<n:
  11.             #j is in bound
  12.             if j<n:
  13.                 #you have found that pair has sum<k
  14.                 if arr[i]-arr[j]<k:
  15.                     ans+=arr[i]+arr[j]
  16.                     i,j=i+2,j+2
  17.                 #you didnt find j than checking for j+1 is waste since they
  18.                 # are in decreasing order.So move to i+1
  19.                 else:
  20.                     i=i+1
  21.                     j=i+1
  22.             #j has reached out of bounds so increment i
  23.             else:
  24.                 i=i+1
  25.                 j=i+1
  26.         return ans
Add Comment
Please, Sign In to add comment