Solution by rohitnandi12


  • 0
    R

    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))$$.


Log in to reply
 

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