aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-04-19 00:06:47 -0600
committerJack Sangdahl <[email protected]>2025-04-19 00:06:47 -0600
commit2e01488b5f45d49e16b116f2b0c858c69bd0dd26 (patch)
tree51764da336ff6fa61711fd94095622ced8bd89e8
parente8ccee285b5d5665cc3d3800c163e942c67c435d (diff)
downloadleetcode-2e01488b5f45d49e16b116f2b0c858c69bd0dd26.tar.gz
leetcode-2e01488b5f45d49e16b116f2b0c858c69bd0dd26.zip
2563. count the number of fair pairs
-rw-r--r--count_num_fair_pairs.c51
-rw-r--r--count_num_fair_pairs.py5
2 files changed, 17 insertions, 39 deletions
diff --git a/count_num_fair_pairs.c b/count_num_fair_pairs.c
index 80d26f1..9ddfc9a 100644
--- a/count_num_fair_pairs.c
+++ b/count_num_fair_pairs.c
@@ -7,46 +7,25 @@
* i < j < n' and 'lower <= nums[i] + nums[j] <= upper'
*/
-int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; }
-
-int bs_lower(int *nums, int n, int left, int right, int lower) {
- int l = left, r = right;
- if (nums[r] < lower)
- return -1;
- while (l < r) {
- int m = l + (r - l) / 2;
- if (nums[m] < lower)
- l = m + 1;
- else
- r = m;
- }
- return l;
-}
-
-int bs_upper(int *nums, int n, int left, int right, int upper) {
- int l = left, r = right;
- if (nums[l] > upper)
- return -1;
- while (l < r) {
- int m = r - (r - l) / 2;
- if (nums[m] > upper)
- r = m - 1;
- else
- l = m;
- }
- return l;
+int cmp(const void *a, const void *b) {
+ return (*(int *)a > *(int *)b) - (*(int *)b > *(int *)a);
}
long long countFairPairs(int *nums, int numsSize, int lower, int upper) {
- int n = numsSize;
+ qsort(nums, numsSize, sizeof(int), cmp);
long long ans = 0;
- qsort(nums, n, sizeof(int), cmp);
- for (int i = 0; i < n - 1; i++) {
- int left = bs_lower(nums, n, i + 1, n - 1, lower - nums[i]);
- int right = bs_upper(nums, n, i + 1, n - 1, upper - nums[i]);
- if (left != -1 && right != -1)
- ans += right - left + 1;
- }
+ int i = 0, j = numsSize - 1;
+ while (i < j)
+ if (nums[i] + nums[j] < lower)
+ ans -= j - i++;
+ else
+ j--;
+ i = 0, j = numsSize - 1;
+ while (i < j)
+ if (nums[i] + nums[j] <= upper)
+ ans += j - i++;
+ else
+ j--;
return ans;
}
diff --git a/count_num_fair_pairs.py b/count_num_fair_pairs.py
index 5933dbd..8d02562 100644
--- a/count_num_fair_pairs.py
+++ b/count_num_fair_pairs.py
@@ -19,9 +19,8 @@ class Solution(object):
nums.sort()
ans = 0
for i in range(len(nums) - 1, -1, -1):
- v = nums[i]
- a = bisect.bisect_left(nums, lower - v, lo=0, hi=i)
- b = bisect.bisect_right(nums, upper - v, lo=0, hi=i)
+ a = bisect.bisect_left(nums, lower - nums[i], i + 1)
+ b = bisect.bisect_right(nums, upper - nums[i], i + 1)
ans += b - a
return ans