Find Pair – Navid's Blog

Find pair such (a,b) meet condition x ≤(a+b)≤ y;

first line n x y
2nd line a[i]

discarding other and taking pair of two element

this is the main equation, we have to remove such pair(ai,aj) so the rest of the array element sum will be fulfill the equation

so we rearranged the equation, multiplied -1 to change equality sign

now problem become easy we have to find only the (ai, aj)

#include <bits/stdc++.h>
#define fast_io                       \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);
#define int long long // Define int as long long
#define pb push_back
#define all(v) v.begin(), v.end()
#define nl "\n"
using namespace std;

void solve()
{
    int n, x, y;
    cin >> n >> x >> y;
    vector<int> a(n);
    for (auto &it : a)
    {
        cin >> it;
    }
    sort(all(a));
    int suma = accumulate(all(a), 0LL);
    x = suma - x;
    y = suma - y;
    int res = 0;
    for (int i = 0; i < n; i++)
    {
        int l = lower_bound(all(a), y - a[i]) - a.begin();
        int r = upper_bound(all(a), x - a[i]) - a.begin();
        res += max(0LL, r - l);
        if (l <= i && i < r)
        {
            // i lies in the range [l,r)
            res--;
        }
    }
    cout << res / 2 << nl;
    // each pair is counted twice
}

int32_t main()
{
    fast_io;
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }

    return 0;
}

We know for pair problem Fixed i and then work with j

Here we Fixed i, then find j . here we can get rang l->r, between l->r all are valid for j. (l-r) will give number of valid a[j] that can be pair with i
But all will be counted twics (i,j) (j,i) so at the end we divided 2

Leave a Comment Cancel Reply