Sqrt(x)

Method 1:
Binary Search

Code:

public class Solution {
    public int mySqrt(int x) {
        if (x < 0) return -1;
        if (x == 0) return 0;
        
        long low = 1;
        long high = x/2+1;
        
        while (low <= high){
            long mid = (low+high)/2;
            if (mid * mid == x) return (int) mid;
            else if (mid * mid < x){
                low = mid + 1;
            }else{
                high = mid -1;
            }
        }
    
        return (int)high;
        
    }
}

Another Method:

Newton method.

[LeetCode] – Binary Search / Math – Pow(x, n)

Problem:

Implement pow(x, n).

Method 1: 

Divide and Conquer. (Dividing n by 2)

Code:

public class Solution {
    public double myPow(double x, int n) {
        if (n == 0) return 1.0;
        if (x == 0.0) return 0.0;
        
        if (n < 0){
            n = -n;
            x = 1/x;
        }
        
        double temp = myPow(x, n/2);
        
        return n%2==0 ? temp*temp: temp*temp*x; 
    }
}

Method 2:

Shifting n to the right.

Code:

public class Solution {
    public double myPow(double x, int n) {
        if (n == 0) return 1.0;
        if (x == 0.0) return 0.0;
        if (n < 0){
            n = -n;
            x = 1/x;
        }
        double res = 1.0;
        while (n > 0){
            if (n%2 == 1){
                res *= x;
            }
            x *= x;
            n >>= 1;
        }
        return res;
    }
}