647. Two Squares That Add Up
Given a non-negative integer n, decide whether there are non-negative integers a and b
with a * a + b * b = n. They may be equal, and either may be zero.
Print Yes or No.
5 -> Yes 1 + 4
4 -> Yes 0 + 4
3 -> No
0 -> Yes 0 + 0
## The search space is tiny
Both a and b are at most sqrt(n), because a square larger than n already exceeds it. So
the candidates are the integers from 0 to floor(sqrt(n)), of which there are about 31623 when
n is 10^9.
Every pair would be O(n) in total. The two-pointer sweep is O(sqrt(n)).
## The sweep
lo = 0, hi = floor(sqrt(n))
while lo <= hi:
s = lo*lo + hi*hi
s == n -> Yes
s < n -> lo += 1
s > n -> hi -= 1
No
The values lo*lo increase with lo and hi*hi decrease as hi falls, so this is exactly
problem 605 run over the squares rather than over an array.
## Why lo <= hi and not lo < hi
a and b may be EQUAL, so the pointers must be allowed to meet. n = 2 is 1 + 1 and
n = 0 is 0 + 0; both are found only when the loop runs with lo == hi.
Writing lo < hi, which is right in problem 605 where two distinct positions are wanted,
answers No on both. This is the clearest example in the topic of a loop bound following from
the PROBLEM rather than from habit.
## Computing the starting hi
Use an integer square root, or take floor(sqrt(n)) from a floating point routine and then
correct it: while hi*hi > n decrease hi, and while (hi+1)*(hi+1) <= n increase it.
At n = 10^9 a double is exact enough, but the correction costs two comparisons and removes
the question entirely. Being in the habit of correcting a floating point square root is worth
more than the two lines cost.
## Overflow
hi*hi is at most n, so nothing exceeds 10^9 inside the loop. But during the correction
(hi+1)*(hi+1) can slightly exceed it, so use 64 bits and the question does not arise.
## Boundaries
0 answers Yes. 1 answers Yes as 0 + 1. 3 is the smallest No.
## Cost
Time O(sqrt(n)). Space O(1).
Constraints - `0 ≤ n ≤ 10^9`
Input
One line containing a single integer n.
Output
Print Yes or No on one line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.