Math #1 : Binary Search - GSC Triple Threat 2020

Does a Solution Exist??

Problem Statement - here

Problem - You are given a positive integer z, and you need to find if there exist two positive integers x, and y such that the given equation is satisfied.

Input:
The first line of input contains T denoting the number of testcases. T testcases follow. Each testcase contains a single line of input containing z.

Output:
For each testcase, in a new line, print "Yes"(without quotes) if the equation can be satisfied, else print "No" (without quotes).

Constraints:
1 <= T <= 100
1 <= z <= 263-1

Solution : 

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.

Onc 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!

Here is the code : 

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;

}