Login
POTD #16 – Count Pairs whose sum is less than target | Geeks For Geeks
5 January 2025 at 17:13
Problem Statement
Geeks For Geeks : https://www.geeksforgeeks.org/problems/count-pairs-whose-sum-is-less-than-target/1
Given an array arr[] and an integer target. You have to find the number of pairs in the array whose sum is strictly less than the target.
Input: arr[] = [7, 2, 5, 3], target = 8 Output: 2 Explanation: There are 2 pairs with sum less than 8: (2, 5) and (2, 3).
Input: arr[] = [5, 2, 3, 2, 4, 1], target = 5 Output: 4 Explanation: There are 4 pairs whose sum is less than 5: (2, 2), (2, 1), (3, 1) and (2, 1).
My Approach
Sorted the array and used two pointer approach to find the possible pairs.
class Solution:
#Complete the below function
def countPairs(self, arr, target):
#Your code here
arr.sort()
n = len(arr)
cnt = 0
left = 0
right = n - 1
while right > left:
if arr[right] + arr[left] < target:
cnt += right - left
left += 1
elif arr[right] + arr[left] >= target:
right -= 1
return cnt
