You are not logged in. Please login at www.codechef.com to post your questions!

×

[closed] need help with spoj problem tiptop

problem link

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.

asked 25 Sep '15, 15:26

dragonemperor's gravatar image

3★dragonemperor
89321135
accept rate: 10%

closed 27 Sep '15, 13:29

The question has been closed for the following reason "The question is answered, right answer was accepted" by dragonemperor 27 Sep '15, 13:29


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.

link

answered 25 Sep '15, 16:10

xellos0's gravatar image

7★xellos0
5.9k54394
accept rate: 10%

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.

(25 Sep '15, 16:35) shubhambhattar3★

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).

(25 Sep '15, 17:16) xellos07★

Got it. Thanks for the explanation.

(25 Sep '15, 17:24) shubhambhattar3★

@xellos0 sorry for late reply. Thank you for your answer. Learned a new thing.

(27 Sep '15, 13:28) dragonemperor3★

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,138
×6

question asked: 25 Sep '15, 15:26

question was seen: 747 times

last updated: 27 Sep '15, 13:29