Solution by rohitnandi12

• Primary Thougths

You may have the thought of coding the "long division method", which is manual steps of calculating a square root. Soon you are going to find that it is complicated to implement and what is complicated isn't the right solution.

If you are a nerd, you may try to use Newton Square root method, it is good but it is slow and it is better where you need the answer to some decimal point.

Since √n-1 < √n < √n+1 , you can use algorithm similar to Binary Search. Pay special attention to boundary conditions. The maximum range of solution can be from -2147483648 <= ans <= 46340, because square root of √Integer.MAX_VALUE is 46340. Hence Square of 46341 is going to cross the 32-bit integer range ( Even I got to know this after few submissions,but its OK, this is learning time :P ).

Test Cases

Try to create your own test cases.

``````T1 : x<2    // x
T2 : 3      // 1
T3 : 2147483647   //46340

``````

Approach #1 Binary Division

Java

``````class Solution {
public int mySqrt(int x) {
if(x<2) return x;

int start = 1;
int end = 46340;
int mid,sq;
while(start<end){
mid = start + (end - start)/2;
sq = mid*mid;

if(sq == x)return mid;
else if(sq>x) end = mid-1;
else start = mid+1;

}

return start*start>x?start-1:start;
}
}
``````

Complexity Analysis

• Time complexity : \$\$O(log n)\$\$.

• Space complexity : \$\$O(1))\$\$.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.