Binary Search – GSC Triple Threat 2020

Problem Statement – here

Given the range of z, it appears that multiple test cases are there so, there must be some time solution…

But there is indeed no constant time solution…the equation reduces to finding the solution of x*x + y*y  = z where both x&y are positive integers. By the heading of the post, it is clear that we will apply a binary search for finding the solution. BUT, why does it work?

Assume 2 pointers -> i and j. Let x,y be the values satisfying x*x + y*y = z.Currently: i < = x and j >=y

so, whenever we have i*i + j*j > z; we will decrease our j. we cannot decrease our i because the optimal value (x) is still greater than i. Whenever we have i*i + j*j < z; we will increase our i. we cannot increase j because the optimal value (y) is still greater than j. One can see that we will converge to the solution fairly easily. Something that is new here is we are handling 2 pointers without a mid for our binary search!

void solve()
{
    // Here ll means long long int
    ll n;
    cin>>n;
    ll low = 1;
    ll high = ceil(sqrt(n));
    bool flag = 0;
    while(low<=high){
        ll val = low*low + high*high;
        if (val == n){
            flag = 1;
            break;
        }
        else if (val < n) low++;
        else high--;
    }
    if (flag) cout << "Yes" << endl;
    else cout << "No" << endl;

}

Leave a Reply