Maximum no. of repeated square root operations that can be performed on a no. in the range?

general
,
1

Given a range of integers [A…B] you have to find the maximum no. of repeated square root operations that can be applied on a no. in the range.

2<=A,B<=1000000000

Ex: A=10 B=20

sqrt(16)=4
sqrt(4)=2
Ans=2

2 is the maximum no. or repeated square root operations that you can have for the given range.

EX: A=6000 B=7000
sqrt(6561)=81
sqrt(81)=9
sqrt(9)=3

3 is the maximum no. or repeated square root operations that you can have for the given range.

my solution: https://pastebin.com/Pgak4xM8

complexity of my solution: O(M sqrt(N))

M: no. of perfect squares in the range 2..1000000000
N: max value in the range

What could be the most optimized way to solve this problem?
is there any chance of improvement in this?

2

Please share a link to the problem so that one can assist you without violating the Code of Conduct.

3

@akashbhalotia

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.

4

@l_returns @vijju123 @kauts_kanu @nik_84 @soham1234 @shivamg_isc @roll_no_1 @rajput1999 @meooow @mayank2510

kindly help me on this.

5

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

  1. the smallest square number \geq A and also
  2. 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)) ?

1 Like
6

@akashbhalotia

Because I think the calOperation(int x) method in my code will take O(sqrt(N)) and that’s how I derived the complexity of (Msqrt(N)).

Am I wrong?

And can you please suggest a more faster way of doing this.

7

I got TLE for this

8

Hi, yes, you seem to be incorrect. Take a look at https://cs.stackexchange.com/questions/6901/what-is-the-time-complexity-of-the-following-program . Your function reduces by a factor of sqrt of input everytime.

Did you run my method? Is it still giving TLE?

9

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.

Python code

10

@akashbhalotia

Since you said I have already done the same thing which you had suggested, so I haven’t tried your code.

11

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

A \leq x^{2^{N}} \leq B
\sqrt{A} \leq x^{2^{N-1}} \leq \sqrt{B}
\sqrt{\left \lceil{\sqrt{A}}\right \rceil} \leq x^{2^{N-2}} \leq \sqrt{\left \lfloor{\sqrt{B}}\right \rfloor}

and so on keep taking square root till inequality holds and the number of steps you can able to do is the answer.

Time Complexity of this solution : \mathcal{O}(\log_2\log_2M)