Let the maximum number in the range be N. Then the number of perfect squares, M will be sqrt(N).
Thus, the complexity of your approach, as you say, is O(M^2).
I was able to improve this to O(MlogM) precomputation, and O(M) per test case.
My code : here
EXPLANATION:
Precompute all the square numbers and the number of steps to reach them. Store them, along with their score in a HashMap. Also add them to an array for easy access later. Sort the array. Thus we have a list of all square numbers in space O(M), time O(MlogM).
Now, for each query, we have A and B. We need to find
the smallest square number \geqA and also
the greatest square number \leqB
I have done this in my code using the variables lo and hi. After getting these numbers, we can just iterate from lo to hi in the array, maintain a max variable for the answer and find the score of all square numbers in the range using the map we had made earlier.
EDIT:
After looking at your code, it seems that you have done the same thing as me. The complexity of your code seems to be O(MlogM) (Due to sorting). Am I missing something? Why did you think the complexity was O(Msqrt(N)) ?
This works by finding the smaller and larger numbers whose squares are within the given interval (including the ends). This constitutes one square root operation. Then these numbers form the new interval and the process is repeated. It stops when the interval becomes degenerate (end point smaller than start point). Seems to work in test cases I tried.
An observation is that every number from range A to B converges to a number which is not a perfect square let this number is x…
A number Z after say N square roots will stop at x i.e. Z = x^{2^{N}}
So for some x we have to find a maximum N such that
A \leq x^{2^{N}} \leq B
\log_2 (log_x A) \leq N \leq \log_2 (log_x B)
For fixed x, we have N = \left \lfloor{\log_2 \left \lfloor{log_x B} \right \rfloor} \right \rfloor if N \geq \left \lceil{\log_2 \left \lceil{log_x A}\right \rceil} \right \rceil
else no N exists…
Now what should be the value of x, basically iterate x from 2 to \sqrt{B} and for every ans of N take maximum of them (for x>\sqrt{B} the N = \left \lfloor{\log_2 \left \lfloor{log_x B} \right \rfloor} \right \rfloor = 0)
Time Complexity : \mathcal{O}(\sqrt{M}*costOfComputingLogs)
Edit:
Above solution involves computing \log functions. Solution by @glenngould doesn’t do so… and also it is very efficient
It works as we have to find a N for some x such that
I received the problem in one personalized contest of 1 hr, I posted it here after submitting my solution there. During contest I couldn’t come up with the approach better then this one, hence I posted here.
One solution for this would be to recursively compute the square roots of the range.
For Example :
Input : 10 20
Iterations :
10 20 -> 4 4 (Successfully found a perfect square in this range -> Add 1 to result)
4 4 -> 2 2 (Successfully found a perfect square in this range -> result = 2)
2 2 -> 1 0 (No perfect squares in range -> result = 2)
Please find below the solution in java :
public int solve(int A, int B) {
if (A > B) {
return 0;
}
int sqrtA = (int)Math.ceil(Math.sqrt(A));
int sqrtB = (int)Math.floor(Math.sqrt(B));
if (sqrtA > sqrtB) {
return 0;
}
return 1 + solve(sqrtA, sqrtB);
}
I am unable to exactly find the complexity of this solution. But, I guess its around O(log N).
Please suggest if any other optimizations are possible.
An iterative solution, complexity o(h) where h is the maximum depth of square root possible within the given range.
public static int solution(int a, int b) {
int count = 0;
while (a <= b) {
int m = (int) (Math.ceil(Math.sqrt(a)));
int n = (int) (Math.floor(Math.sqrt(b)));
if (m == a && n == b)
break;
a = m;
b = n;
if (a <= b)
count++;
}
return count;
}