## Friday, March 18, 2016

### Number of perfect squares between two given numbers - GeeksforGeeks

Number of perfect squares between two given numbers - GeeksforGeeks
Given two given numbers a and b where 1<=a<=b, find the number of perfect squares between a and b (a and b inclusive).
```Input : a = 9, b = 25
Output : 3
The three squares in given range are 9,
16 and 25```
Method 2 (Efficient) We can simply take square root of ‘a’ and square root of ‘b’ and count the perfect squares between them using
```floor(sqrt(b)) - ceil(sqrt(a)) + 1

We take floor of sqrt(b) because we need to consider
numbers before b.

We take ceil of sqrt(a) because we need to consider
numbers after a.

For example, let b = 24, a = 8.  floor(sqrt(b)) = 4,
ceil(sqrt(a)) = 3.  And number of squares is 4 - 3 + 1
= 2. The two numbers are 9 and 16.```
`    ``double` `countSquares(``int` `a,``int` `b)`
`    ``{`
`        ``return` `(Math.floor(Math.sqrt(b)) -`
`                ``Math.ceil(Math.sqrt(a)) + ``1``);`
`    ``}`

Time complexity of this solution is O(Log b). A typical implementation of square root for a number n takes time equal to O(Log n)

`    ``static` `int` `countSquares(``int` `a, ``int` `b)`
`    ``{`
`        ``int` `cnt = ``0``; ``// Initialize result`

`        ``// Traverse through all numbers`
`        ``for` `(``int` `i=a; i<=b; i++)`

`            ``// Check if current number 'i' is perfect`
`            ``// square`
`            ``for` `(``int` `j=``1``; j*j<=i; j++)`
`                ``if` `(j*j==i)`
`                    ``cnt++;`
`        ``return` `cnt;`
`    ``}`
http://www.geeksforgeeks.org/square-root-of-an-integer/
Better Solution to do Binary Search.
```Let  's' be the answer.  We know that 0 <=  s <= x.

Consider any random number r.

If r*r <= x, s >= r

If r*r > x, s < r.
```
Algorithm:
1) Start with 'start' = 0, end = 'x',
2) Do following while 'start' is smaller than or equal to 'end'.
a) Compute 'mid' as (start + end)/2
b) compare mid*mid with x.
c) If x is equal to mid*mid, return mid.
d) If x is greater, do binary search between mid+1 and end. In this case, we also update ans (Note that we need floor).
e) If x is smaller, do binary search between start and mid-1
Time Complexity: O(Log x)
Note: The Binary Search can be further optimized to start with 'start' = 0 and 'end' = x/2. Floor of square root of x cannot be more than x/2 when x > 1.
`    ``public` `static` `int` `floorSqrt(``int` `x)`
`    ``{`
`        ``// Base Cases`
`        ``if` `(x == ``0` `|| x == ``1``)`
`            ``return` `x;`

`        ``// Do Binary Search for floor(sqrt(x))`
`        ``int` `start = ``1``, end = x, ans=``0``;`
`        ``while` `(start <= end)`
`        ``{`
`            ``int` `mid = (start + end) / ``2``;`

`            ``// If x is a perfect square`
`            ``if` `(mid*mid == x)`
`                ``return` `mid;`

`            ``// Since we need floor, we update answer when mid*mid is`
`            ``// smaller than x, and move closer to sqrt(x)`
`            ``if` `(mid*mid < x)`
`            ``{`
`                ``start = mid + ``1``;`
`                ``ans = mid;`
`            ``}`
`            ``else`   `// If mid*mid is greater than x`
`                ``end = mid - ``1``;`
`        ``}`
`        ``return` `ans;`
`    ``}`

Simple Solution to find floor of square root is to try all numbers starting from 1. For every tried number i, if i*i is smaller than x, then increment i. We stop when i*i becomes more than or equal to x.
`int` `floorSqrt(``int` `x)`
`{`
`    ``// Base cases`
`    ``if` `(x == 0 || x == 1)`
`       ``return` `x;`

`    ``// Staring from 1, try all numbers until`
`    ``// i*i is greater than or equal to x.`
`    ``int` `i = 1, result = 1;`
`    ``while` `(result < x)`
`    ``{`
`       ``if` `(result == x)`
`          ``return` `result;`
`       ``i++;`
`       ``result = i*i;`
`    ``}`
`    ``return` `i-1;`
`}`
Read full article from Number of perfect squares between two given numbers - GeeksforGeeks