# Counting Squares In a Range

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.

The problem:

"For 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?

• Do you mean the number of squares between $A$ and $B$? – Edward Evans Apr 18 '16 at 15:25
• @Ed_4434 Inclusive, yes. Apologies if my formatting isn't clear :) – levelonehuman Apr 18 '16 at 15:52

I presume $A$ and $B$ are positive integers. The number of squares $\le B$ is $\lfloor \sqrt{B} \rfloor$. The number of squares $< A$ is the number of squares $\le A-1$, and thus $\lfloor \sqrt{A-1}\rfloor$. The number between $A$ and $B$ (inclusive) is the difference between these.

EDIT: But this is not the same as " sqrt(B) - sqrt(A - 1) rounded down". For example, take $A = 3$, $B = 4$. There is one square ($4$) between $A$ and $B$, inclusive, but $\lfloor \sqrt{4} - \sqrt{2}\rfloor = 0$.

• I understand that this is the case, I just don't know why that is. Is there some mathematical property/theory/law/etc that explains why the square root of $B$ is the number of squares <= B? – levelonehuman Apr 18 '16 at 15:55
• @levelonehuman if you take all the integers $i <= \sqrt B$ and square them, you will get a list of squares that range from $i^2 : B$ – J. Bush Apr 18 '16 at 15:57
• The critical observation is that squaring is monotonic: that $x \lt y \iff x^2 \lt y^2$ This justifies the first sentence of the answer. – Ross Millikan Apr 18 '16 at 15:57
• I added a note to the question in response to your edit. I'm (obviously?) not very well versed in math notation/concepts/etc. Thanks for your explanation! – levelonehuman Apr 18 '16 at 16:02

To understand why this is the answer, let's start off with a simpler. Lets take a look at the number of perfect squares between $0$ and $B$. What more, let's assume that $B$ is a perfect square, meaning there exists $C$ such that $C^2=B$.

How many perfect squares are there between $0$ and $B$? There are exactly $C$ - for each integer from 1 to $C$ we have a square number.

Let's now assume $B$ is between $C^2$ and $(C+1)^2$. How many square numbers are there between $0$ and $B$ this time? We definitely have $C$ numbers, since $C^2 < B$. The $C+1$-th number is too big, however, to contribute to the total - that leaves us with exactly $C$ perfect squares. Let us notice that $\sqrt B\in(C, C+1)$, from which $\lfloor \sqrt B \rfloor = C$.

So now we return to the original question: we know that from $0$ to $A$ we have $\lfloor \sqrt A \rfloor$ perfect squares. From $0$ to $B$ we have $\lfloor \sqrt B \rfloor$ perfect squares. So from $A$ to $B$ we have as many as there are from $0$ to $B$ minus as many as from $O$ to $A-1$(due to the fact, that we are interested in the perfect squares between $[A,B]$) - that is, $\lfloor \sqrt B \rfloor - \lfloor \sqrt(A - 1) \rfloor$.