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?

1 Like
2

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
3

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

4

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)

5

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

6

@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.

7

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

kindly help me on this.

8

@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.

9

I got TLE for this

10

Hi, yes, you seem to be incorrect. Take a look at algorithm analysis - What is the time complexity of the following program? - Computer Science Stack Exchange . Your function reduces by a factor of sqrt of input everytime.

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

11

@akashbhalotia

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

12

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.

1 Like
13

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;
	}
15

I was also asked this problem. I came up with this solution.

    public class MaxSqRootProblem {
static int getCountOfSquareRoots(double num){
    double sqrt = Math.sqrt(num);
    if(sqrt % 1 != 0){
        return 0;
    }
    else{
        return 1 + getCountOfSquareRoots(sqrt);
    }
}

static int findTheMaximumNumberOfRepeatedSqaureRoots(int A, int B){
    double pointer = A;
    int max_count = 0;

    while(pointer <= B){
        double sqrt = Math.sqrt(pointer);
        if(sqrt % 1 == 0){
            int num = getCountOfSquareRoots(pointer);
            if(num > max_count){
                max_count = num;
            }
        }
        int val = (int) (sqrt / 1) + 1;
        pointer = val * val;
    }

    return max_count;
}


public static void main(String[] args) {
    System.out.println(MaxSqRootProblem.findTheMaximumNumberOfRepeatedSqaureRoots(2,2000000));
}

}

16

Tried something like this to fetch the count value for repeated square root operations. But how do I ensure if it is efficient ?

package com.sqrt;

import java.util.Scanner;

public class Squareroot
{

public static void main(String[] args)
{
	 System.out.println("Enter 1st number");
	 Scanner sc = new Scanner(System.in);
	 int i=sc.nextInt();
	 System.out.println("Enter 2nd number");
	 int j=sc.nextInt();
	 int count=1;
     for(int k=i;k<j;k++)
     {
    	double z=Math.sqrt(k);
    	
    	if(z-Math.floor(z)==0)
    	{
    		double s=Math.sqrt(z);
    	
    		if(s-Math.floor(s)==0)
    		{
    		// System.out.println(s);
    		 count++;
    		 
    		 double p=Math.sqrt(s);
    		 if(p-Math.floor(p)==0)
    		 {
    		//	 System.out.println(p);
    			 count++;
    		 }
    		}
    		
    	}
    }
  
    System.out.println("count is " + count);
}

}

17

What about cache magic Java-sandbox/MaxSqrt.java at master · Olezha/Java-sandbox · GitHub