# Programming Interview Questions 27: Squareroot of a Number

Find the squareroot of a given number rounded down to the nearest integer, without using the sqrt function. For example, squareroot of a number between [9, 15] should return 3, and [16, 24] should be 4.

The squareroot of a (non-negative) number N always lies between 0 and N/2. The straightforward way to solve this problem would be to check every number k between 0 and N/2, until the square of k becomes greater than or rqual to N. If k^2 becomes equal to N, then we return k. Otherwise, we return k-1 because we’re rounding down. Here’s the code:

def sqrt1(num): if num<0: raise ValueError if num==1: return 1 for k in range(1+(num/2)): if k**2==num: return k elif k**2>num: return k-1 return k

The complexity of this approach is O(N), because we have to check N/2 numbers in the worst case. This linear algorithm is pretty inefficient, we can use some sort of binary search to speed it up. We know that the result is between 0 and N/2, so we can first try N/4 to see whether its square is less than, greater than, or equal to N. If it’s equal then we simply return that value. If it’s less, then we continue our search between N/4 and N/2. Otherwise if it’s greater, then we search between 0 and N/4. In both cases we reduce the potential range by half and continue, this is the logic of binary search. We’re not performing regular binary search though, it’s modified. We want to ensure that we stop at a number k, where k^2<=N but (k+1)^2>N. The code will clarify any doubts:

def sqrt2(num): if num<0: raise ValueError if num==1: return 1 low=0 high=1+(num/2) while low+1<high: mid=low+(high-low)/2 square=mid**2 if square==num: return mid elif square<num: low=mid else: high=mid return low

One difference from regular binary search is the condition of the while loop, it’s low+1<high instead of low<high. Also we have low=mid instead of low=mid+1, and high=mid instead of high=mid-1. These are the modifications we make to standard binary search. The complexity is still the same though, it’s logarithmic O(logN). Which is much better than the naive linear solution.

There’s also a constant time O(1) solution which involves a clever math trick. Here it is:

$\sqrt{N} = N^{0.5} = 2^{log_2N^{0.5}} = 2^{0.5log_2{N}}$

This solution exploits the property that if we take the exponent of the log of a number, the result  doesn’t change, it’s still the number itself. So we can first calculate the log of a number, multiply with 0.5, take the exponent, and finally take the floor of that value to round it down. This way we can avoid using the sqrt function by using the log function. Logarithm of a number rounded down to the nearest integer can be calculated in constant time, by looking at the position of the leftmost 1 in the binary representation of the number. For example, the number 6 in binary is 110, and the leftmost 1 is at position 2 (starting from right counting from 0). So the logarithm of 6 rounded down is 2. This solution doesn’t always give the same result as above algorithms though, because of the rounding effects. And depending on the interviewer’s perspective this approach can be regarded as either very elegant and clever, or tricky and invalid. But in any case it definitely worths mentioning, ultimately it proves that you’re aware of math shortcuts. Which is always a desired talent in every job candidate.

VN:F [1.9.22_1171]
Programming Interview Questions 27: Squareroot of a Number, 8.5 out of 10 based on 53 ratings
This entry was posted in Programming Interview. Bookmark the permalink.
• hold

Wtf. The algos here are so retarded I am not sure how the hell you manage of do what you do.
The simplest way of doing this (without sqrt or log or any fancy functions) is via Newton Iteration.

• sonesh

ohh man
The number N(integer) is either a square of some integer or not, if not then we just have to ans. not exist, other wise that number (integer) t such that t*t = N

• Oguz

Think about what happens if they give you a double as an input, do your answer still guarantee the correct result?

• MD

in case of double, it won’t work because arden is saying that “the result should be between 0 and N/2”. However, if the number N is between 0 and 1, the result is definitely greater than N/2. For Example if N=0.2, the result should be greater than 0,2 and not between 0 and N/2

• http://ivanzuzak.info Ivan Zuzak

Hi Arden,

for the first approach you write “The complexity of this approach is O(N), because we have to check N/2 numbers in the worst case.”. While this is true (since O(N) definitely is an upper bound), we can make it even more precise — the complexity of this approach is O(sqrt(N)) since you will check at least sqrt(N) numbers and at most sqrt(N)+1 numbers. In a way, the N/2 bound and the iterative loop from 0 to N/2 misleads us to think that the time complexity is linear, while in fact it is not because we will never go all the way up to N/2 (we will stop at sqrt(N)+1).

Until I got this question on one of my interviews, I also thought that the time complexity was linear, but my interviewer set me straight. :)

Awesome series of blog posts, btw. One of the best I’ve seen on technical interview questions!

Replica also initiates pumps with the red sole and these pumps are elevated popular
Julie J. Bailey

• MD

Hi Arden, Thanks a lot for posting this question. I think there is something missing.
The square root of a number N is always between 0 and N/2. However, if 0<N<1, IN this case sqrt(N) is larger than N itself and that is not covered in your code. am I right ?

• MD

sorry the text was corrupted. my point is if 0<N<1, sqrt(N) is not between 0 and N/2 but greater than N itself.

• MD

again ?? what’s going on ?

• MD

Arden, we should add a case that if Number N is greater than 0 and less than 1, set High=1

• Ramesh

The squareroot of a (non-negative) number N always lies between 0 and N/2. This is not correct. N = 3, square root of 3 is 1.732

• Petra

It is valid for every greater or equal to 4. In this implementation, it doesn’t matter as you’re not looking for an exact square root, but smaller int.

• Anonymous Coward

I think I have a simpler solution that is the same log2(n) complexity. I say it’s simpler because there is much less room for error in coding it.
public double sqrRoot(double n) {
assert(n >= 0);
double tolerance = 0.001;
double half = (n / 2.0d);
double mult = n / half;

while (Math.abs(half – mult) > tolerance) {
//half = (half + mult) / 2.0; //possible overflow. Use custom ‘mid()’ function.
half = mid(half, mult);
mult = n / half;
}
return half;
}

• Anonymous Coward

If you wanted the solution using integers only, the same algorithm applies:
public long sqrRoot(long n) {
assert(n >= 0);
long half = n >> 1;
long mult = n / half;

while (Math.abs(mult – half) > 1) {
half = mid(mult, half);
mult = n / half;
}
return half > mult ? mult : half;
}

• vrg

Hi

Any reason why you are calculating mid using
mid=low+(high-low)/2 for calculating mid?

if we solve mid=low+(high-low)/2 we will get mid= (low+high)/2.

why are you not directly using mid= (low+high)/2. in the code?

Thanks

• priyanshu2501

(low+high)/2 may result in wrong mid in case low and high are large numbers.(~1e9)
Prevented by using low + (high-low)/2

• HyungJun Lim

Calculating mid ** 2 for large input causes mid ** 2 to be larger than int64 range. (At least it did in Java).

• Kamal Chaya

Why is it low+1 instead of low?