2
$\begingroup$

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?

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

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

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ – levelonehuman Apr 18 '16 at 15:55
  • $\begingroup$ @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$ $\endgroup$ – J. Bush Apr 18 '16 at 15:57
  • $\begingroup$ 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. $\endgroup$ – Ross Millikan Apr 18 '16 at 15:57
  • $\begingroup$ 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! $\endgroup$ – levelonehuman Apr 18 '16 at 16:02
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.