Perfect Squares between two numbers

x = (int)sqrt(n2) - (int)sqrt(n1);

Its trivial. Assume you have two endpoints, a & b, with a < b.

  1. What is the next perfect square after a? Hint, what is sqrt(a)? What would rounding up do?

  2. What is the largest perfect square that does not exceed b? Hint, what is sqrt(b)? Again, how would rounding help here?

Once you know those two numbers, counting the number of perfect squares seems truly trivial.

By the way, be careful. Even the sqrt of 2^60 is a big number, although it will fit into a double. The problem is that 2^60 is too large to fit into a standard double, since it exceeds 2^53. So beware precision issues.

Tags:

Algorithm

C++