2/1 some Math problems

divide two integers()

The intuitive way of using addtion to divide two integers works. We eastablish variables sum and quotient with the invariant quotient * divisor = sum. Take 20 / 3 for example,

sum  quotient  target
3     1        17
6     2        14
9     3        11
12    4        8
15    5        5
18    6        2
 ^
 18 + 3 > 20, so the answer is 6

To increase quotient one by one costs much time. We could apply Binary Search here, i.e. quotient = quotient * 2 each time.

sum  quotient  target
3     1        17
6     2        14
12    4        8
 ^
 12 + 12 > 20, so the answer is 4 --- X wrong for we missed quotient of 8 / 3
Instead, 
sum  quotient  target
3     1        8
6     2        5
^
6 + 6 > 8, so the answer for 8 / 3 is 2

The final answer is 4 + 2 = 6

We remove negative sign of dividend and divisor in the beginning and add signNegative to make up the difference. In case of Integer Overflows, we use long to while addition. And we need to make sure the final result is within the range [−2^31, 2^31 − 1].

class Solution {
    public int divide(int dividend, int divisor) {
        int sign = 1; 
        if ((dividend > 0 && divisor < 0) && (dividend < 0 && divisor > 0)) sign = -1;

        long divd = Math.abs((long) dividend);
        long divs = Math.abs((long) divisor);

        long res = divideRecur(divd, divs);

        if (res > Integer.MAX_VALUE && sign > 0) {
            // dividend = -21...8   divisor = -1
            return Integer.MAX_VALUE;
        }

        if (sign > 0) return (int)res;
        return (int)(-res);
    }

    private long divideRecur(long dividend, long divisor) {
        if (dividend < divisor) {
            return 0;
        }

        long sum = divisor, quotient = 1;
        while (sum + sum < dividend) {
            sum += sum;
            quotient += quotient;
        }
        return quotient + divideRecur(dividend - sum, divisor);
    }
}

pow()

有几点需要注意：

• the exponent can be positive or negative. we will process absolute value first, and consider the sign in the end;
• $$101 = 1(2^2) + 0(2^1) + 1*(2^0); x^5 = (x^4)^1 (x^2)^0 (x^1)^1$$ , firstly process the least significant bits and then multiply the $$x^1$$to the result.
• x^5 how to say? x to the fifth. or formal, x to the fifth power.

class Solution {
    public double myPow(double x, int n) {
        long abs = Math.abs((long)n);
        double res = 1.0;
        while (abs != 0) {
            if ((abs & 1) != 0) {
                res *= x;
            }
            x *= x;
            abs >>= 1;
        }
        return (n < 0) ? 1 / res : res; 
    }
}

sqrt()

首先这道题我们可以用binary search来做。basic idea is to search from [1, x] to find the greatest i where i * i <= x.

class Solution {
    public int mySqrt(int x) {
        if (x <= 1) return x;

        int low = 1, high = x;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (mid > x / mid) {
                high = mid - 1;
            } else {
                if (mid + 1 > x / (mid + 1)) {
                    return mid;
                }
                low = mid + 1;
            }
        }
        return 0;
    }
}

另外，对于求square root的题，还可以用Newton 迭代来做，非常简洁，但是需要mathematical proof.

在numerical analysis里的多项式求近似值，binary search又称bisection method，收敛速度为liner convergence;而newton's method是quadratic convergence，收敛速度要快很多。for the given mathematical function, if it is a convergent function, it will hold the property that .. for the given xn, the value is f(xn), and the slope of tangent is transitive of f(xn)...

And we know that y - f(xn) = f'(xn)(x - xn). When y = 0, we would get the xn+1 = xn - ... see below.the code for Newton's method is simple:

class Solution {
    public int mySqrt(int x) {
        long i = x;
        while (i * i > x) {
            i = (i + x / i) / 2;
        }
        return (int)i;
    }
}

related problem is valid perfect square:

Given a positive integer num, write a function which returns True if num is a perfect square else False.

class Solution {
    public boolean isPerfectSquare(int num) {
        if (num == 1) return true;
        long i = num;
        while (i * i > num) {
            i = (i + num/i) / 2;
        }
        return i * i == num;
    }
}

sum of square number:

the key is to use two pointers to solve the problem.

class Solution {
    public boolean judgeSquareSum(int c) {
        if (c <= 0) return true;

        int left = 0, right = (int)Math.sqrt(c);
        while (left <= right) {
            int val = left * left + right * right;
            if (val > c) {
                right--;
            } else if (val < c) {
                left++;
            } else {
                return true;
            }
        }
        return false;
    }
}

Count Primes

It's basically marking all the multiples of i as composite. For example, when i = 2, we mark 22, 23, 24 ... as composite, and since we're only interested in the range (0,n), we stop once we reach 2*j >= n. Then, i = 3, and we mark 32, 3*3, .... as composite, again only going up to a number that's <n.

class Solution {
    public int countPrimes(int n) {
        boolean[] notPrime = new boolean[n];
        int count = 0;
        for (int i = 2; i < n; ++i) {
            if (notPrime[i] == false) {
                count++;
                for (int j = 2; i * j < n; ++j) {
                    notPrime[i * j] = true;
                }
            }
        }
        return count;
    }
}

Maximal Square

Max Points on a Line

Line Reflection