This problem is posted on Hackerrank as part of 20/20 Hack March 2014.
If you do not want to read the solution and you want to solve the problem on your own, Click on the link. If you want to know the solution for the problem, read on…
For example, if the given range is [1,5] the number of perfect squares in this range is 2 (including the lower and upper bounds)
1= 12 and 4 = 22
Simple solution:
The obvious solution is to check if each number in the given range is a perfect square or not. This runs O(n) time. For a small range of numbers, this works fine. But for a big range, this takes a lot of time.
Can we improve this solution further?
We can improve this as follows.
First we find the square roots of lower bound and and upper bounds. The difference between them gives the required number.
For example consider the range [2,11]
sqrt(2) = 1.414
sqrt(11) = 3.316
If you round them off, and take the difference (3-1), it is 2 which is the required answer.
However we have to handle two special cases.
Case 1: Lower and upper bounds are same.
For example [4, 4]. In this case we have to check if the given number is a perfect square. If it is, output 1, otherwise output 0.
Case 2: If the lower bound is a perfect square.
In this case, we have to add 1 to the diff of square roots.
For example consider [4, 20]; rounded square roots are [2, 4]; the diff is 2. But there are 3 perfect squares in the given range (4, 9, 16).
In all the remaining cases, the number of perfect squares is the difference of the square roots.
Here is the C++ implementation for this problem.