The problem seems straight forward. If the number is a perfect square then yes, otherwise no. But I am getting WA. Then I came across this blog.
I am having trouble with this line
if(ss==n || (s-1)(s-1)==n || (s+1)*(s+1)==n)
In my code, I only used s*s==n. Why are the rest required? I mean s is simply the typecasted value, and has to be less than or equal to the sqrt(n). Correct me if I am wrong.
That’s because sqrt(n) gives a double and doubles are imprecise. It’s possible that you’d get sqrt(9)=2.999… and round it to s=2. In addition, there can be bigger errors with large numbers (since double can only store around 14 digits, long long up to 18). That’s why it’s a good idea to check a few numbers around what sqrt() gives you.
My preferred alternative would be correcting s=sqrt(n) like this:
while(s*s > n) s--;
while((s+1)*(s+1) <= n) s++;
which makes s the largest number such that s*s <= n, regardless of the error sqrt() may make. Now the only thing left is checking if s*s == n.
Why do we need the first line:
while(s*s > n) s–;
If s = sqrt(n), then s can only be less than or equal to the actual square root but never greater than it.
Unnecessary assumption. Don’t assume that double makes sense.
Look at it this way: sqrt() gives you an estimate of the correct number. It’s close enough for this iterative approach to be fast, but you don’t know anything more about it. Not even if the estimate is more or less than the correct number.
As an example, if n gets large enough (10^100), maybe you can have errors in sqrt(n) that are more than ±10. If it’s +10, then sqrt(n) calculated will be more than 10+correct_sqrt(n) and even rounding down would make it more than correct_sqrt(n).
Got it. Thanks for the explanation.