aboutsummaryrefslogtreecommitdiff
path: root/count_num_fair_pairs.c
diff options
context:
space:
mode:
Diffstat (limited to 'count_num_fair_pairs.c')
-rw-r--r--count_num_fair_pairs.c51
1 files changed, 15 insertions, 36 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;
}