15 ms Newton's method in C++ without floating point numbers or long


  • 0
    T

    Trick without long with Newton's method.

       int mySqrt(int x) {
    
            if (x <= 1) {
                return x;
            }
            
            if (x >= 46340 * 46340) { // 46341 * 46341 will just overflow
                return 46340;
            }
            
            int cur = x / 2 > 46340 ? 46340 : x / 2;
            while (cur * cur > x || (cur + 1) * (cur + 1) < x) {
                cur = (x / cur + cur) / 2;
            }
            
            return cur;
        }

  • 0
    T

    This function will be 5ms in C.


Log in to reply
 

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