Adobe OA
Anonymous User
1535
Interview

I'm not able to comeup with solution in given constraints.
image
image

More formally:
You are given l and r where r can be upto 10^12 . you need to return the count of no of pairs such that sqrt(a^2-b) is integral where b lies between l and r (both l and r are inclusive).

edit: Got the Solution thanks to @shubhamjha386

#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    vector<int> squares;
    for (int i = 0; i * i <= 1e12; i++)
        squares.push_back(i * i);
    int n = squares.size();
    int t;
    cin >> t;
    while (t--)
    {
        int l, r;
        cin >> l >> r;
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            int low = lower_bound(squares.begin(), squares.end(), squares[i] + l) - squares.begin();
            int high = lower_bound(squares.begin(), squares.end(), squares[i] + r) - squares.begin();
            if (high == n or (squares[high] - squares[i]) > r)
                high--;
            if (high < low)
                break;
            ans += (high - low + 1);
        }
        cout << ans << "\n";
    }
    return 0;
}
Comments (3)