Constant time c++ solution 8ms


  • 2
    H

    value of b will be maximum 2^16 before entering while loop and while loop will run at most 16 time so constant time.

    class Solution {
     public:
    int mySqrt(int x) 
    {   
        if(x<=1) return x;
        
        int a=0,b,c=x,cnt=0;
        long t,m;
        
        while(c) {c=c/10;cnt++;}
    
        b=pow(10,cnt/2+1);
        
        while(a<b)
        {
            m=(a+b)/2;
            t=m*m;
            if(t==x) return m;
            if(t<x) a=m+1;
            else b=m;
        }
        
        return a-1;
    }
    

    };


Log in to reply
 

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