Robert Eisele
Engineer, Systems Architect and DBA

Hackerrank: Sherlock and Squares

Original Problem

Watson gives two integers (\(A\) and \(B\)) to Sherlock and asks if he can count the number of square integers between \(A\) and \(B\) (both inclusive).

Note: A square integer is an integer which is the square of any integer. For example, 149, and 16 are some of the square integers as they are squares of 123, and 4, respectively.

Input Format

The first line contains \(T\) the number of test cases. \(T\) test cases follow, each in a new line. 
Each test case contains two space-separated integers denoting \(A\) and \(B\).

Constraints

\(1\leq T\leq 100\)
\(1\leq A\leq B\leq 10^9\) 

Output Format

For each test case, print the required answer in a new line.

Sample Input

2
3 9
17 24

Sample Output

2
0

Solution

Let's say we have a square number \(x^2\) within the interval \([A, B]\) and we want to find the number of perfect squares that fall into the interval. We can then calculate the number of squares between two numbers like this:

\begin{array}{rl} & A \leq x^2 \leq B\\ \Leftrightarrow & \sqrt{A} \leq x \leq\sqrt{B}\\ \Leftrightarrow & \sqrt{A} \leq \lceil\sqrt{A}\rceil \leq x \leq \lfloor\sqrt{B}\rfloor\leq\sqrt{B}\\ \Rightarrow & n =\underbrace{\lfloor\sqrt{B}\rfloor}_{\in\mathbb{N}} - \underbrace{\lceil\sqrt{A}\rceil}_{\in\mathbb{N}} + 1 \end{array}

The last line follows from the fact that the distance of two numbers \(a, b\in\mathbb{N}\) with \(a\leq b\) is \(b-a+1\), when the bounds are included.

When implemented in Ruby the formula looks like this:

gets.to_i.times{
 a, b = gets.split.map(&:to_f)
 puts Math.sqrt(b).floor() - Math.sqrt(a).ceil() + 1
}

Go to overview