# Hackerrank Solution: Sherlock and Squares

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, *1*, *4*, *9*, and *16* are some of the square integers as they are squares of *1*, *2*, *3*, 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 }