2699 Count The Number Of Fair Pairs
2699 Count The Number Of Fair Pairs
Count the Number of Fair Pairs 
Given a 0-indexed integer array nums of size n and two integers lower and upper, return the number of fair pairs.
A pair (i, j) is **fair **if:
1
2
0 <= i < j < n, and
lower <= nums[i] + nums[j] <= upper
Example 1:
1
2
3
4
5
**Input:** nums = [0,1,7,4,4,5], lower = 3, upper = 6
**Output:** 6
**Explanation:** There are 6 fair pairs: (0,3), (0,4), (0,5), (1,3), (1,4), and (1,5).
Example 2:
1
2
3
4
5
**Input:** nums = [1,7,9,2,5], lower = 11, upper = 11
**Output:** 1
**Explanation:** There is a single fair pair: (2,3).
Constraints:
1
2
3
4
1 <= nums.length <= 105
nums.length == n
-109 <= nums[i] <= 109
-109 <= lower <= upper <= 109
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
def lower_bound(self, nums, low, high, element):
while low <= high:
mid = low + ((high - low) // 2)
if nums[mid] >= element:
high = mid - 1
else:
low = mid + 1
return low
def countFairPairs(self, nums, lower, upper):
nums.sort()
ans = 0
for i in range(len(nums)):
# Assume we have picked nums[i] as the first pair element.
# `low` indicates the number of possible pairs with sum < lower.
low = self.lower_bound(nums, i + 1, len(nums) - 1, lower - nums[i])
# `high` indicates the number of possible pairs with sum <= upper.
high = self.lower_bound(
nums, i + 1, len(nums) - 1, upper - nums[i] + 1
)
# Their difference gives the number of elements with sum in the
# given range.
ans += high - low
return ans
This post is licensed under CC BY 4.0 by the author.