I've been working on a series of programming challenges to work on my math skills, and I came across a solution that I don't know how to explain.
1 <= A <= B <= 10^9, find the number of perfect squares between $A$ and $B$ (inclusive).
My initial solution was to loop through all the numbers in a range and count the perfect squares that way. However, this was obviously a very slow solution (~ 14 seconds for range 1 -> 10^9).
Then, I came across the following:
"The number of squares between $A$ and $B$ =
sqrt(B) - sqrt(A - 1)rounded down".
NOTE: From an answer to this question,
rounded down is incorrect in this case, but this formula holds for finding the perfect squares in a given range. The code for this question actually converts the value to an
int, which performs rounding to the nearest integer, not necessarily down.
This is cool and offered a vastly quicker solution, but I don't understand why.
Can anyone help me understand why this simple equation actually works?