Sqrt(x) Cont…

Question: Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:

Input: 4
Output: 2

Example 2:

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since 
             the decimal part is truncated, 2 is returned.

You may view the full question here.

Approach 2: Unlike last time, this time let’s try to get some work done. In the previous post, we could gauge the performance of the java provided sqrt() method. It’s probably too ambitious to try and match that right in the first attempt. After ̶a̶ ̶f̶e̶w̶ many many failed attempts, and a day’s sleep to overcome the exhaustion, here’s an approach that may not be the best, but definitely manages to clear all the testcases —

//Approach 2:
//Runtime: 7ms
//Memory usage: 32.5MB
class Solution {
    public int mySqrt(int x) {
        return (int)initial(x);
    }
    
    private double initial(int x){
        int half = 1;
        double full = 10;
        while((int)(x/(full*10))!=0 && (int)(x/(full*100))!=0){
            half*=10;
            full*=100;
        }
        double part = x/half;
        if(full>10){
            while(part*part>x){
                part=part/10;
            }
            int otherPart =(int) (x /(part*part));
            part = part*initial(otherPart);
        }
        return part*part>x?decrement(x, part):increment(x, part);
    }
    
    private double increment(int x, double half){
        while(half*half<x){
            half++;
        }
        if(((double)((int)half)*(double)((int)half))<=x){
            return half;
        }
        return half-1;
    }
    
    private double decrement(int x, double half){
        while(half*half>x){
            half--;
        }
        return half;
    }
}

Find more posts here.

Cheers & Chao!