Greatest Common Divisor

Given an array of Integers, return the greatest common divisor of all the numbers in the array.

/*
time:O(n?), space:O(1)
*/

import java.util.*;

public class Solution {
    public static int gcd(int[] A) {
        if (A == null || A.length <= 1) {
            return 0;
        }
        int num = A[0];
        for (int i = 1; i < A.length; i++) {
            num = calGCD(num, A[i]);
            if (num == 1) {
                return 1;
            }
        }
        return num;
    }
    public static int calGCD(int a, int b) {
        while (a % b != 0) {
            int k = a % b;
            a = b;
            b = k;
        }
        return b;
    }

    public static void main(String[] args) {
        int[] A = {2,3,6,7};
        int res = gcd(A);
        System.out.print(res);
        
    }
}

Rectangle Overlap

Find the total area covered by two rectilinear rectangles in a 2D plane.

Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.

Assume that the total area is never beyond the maximum possible value of int.

/*

There are eight conditions totally. 

time:O(1), space:O(1)

*/

public class Solution {
    public int computeArea(int A, int B, int C, int D, 
                           int E, int F, int G, int H) {
        int l = Math.max(A, E);
        int r = Math.max(l, Math.min(C, G));
        int b = Math.max(B, F);
        int t = Math.max(b, Math.min(D, H));
        return (C - A) * (D - B) + 
               (G - E) * (H - F) - 
               (r - l) * (t - b) ;
    }
}

Add Binary

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

/*

Maintain a variable to store the carry in each calculation.

time: O(n), space: O(1)

*/

public class Solution {

    public String addBinary(String a, String b) {

        if (a == null || a.length() == 0) {

            return b;

        }

        if (b == null || b.length() == 0) {

            return a;

        }

        int aIndex = a.length() - 1;

        int bIndex = b.length() - 1;

        int carry = 0;

        String ans = "";

        while (aIndex >= 0 || bIndex >= 0) {

            int sum = carry;

            if (aIndex >= 0) {

                sum += a.charAt(aIndex) - '0';

            }

            if (bIndex >= 0) {

                sum += b.charAt(bIndex) - '0';

            }

            carry = sum / 2;

            ans = String.valueOf(sum % 2) + ans;

            aIndex--;

            bIndex--;

        }

        if (carry == 1) {

            ans = "1" + ans;

        }

        return ans;

    }

}

Pow(x, n)

Implement pow(x, n).

/*
The naive way is to use a for loop to multiply x every time. 
time:O(n), space:O(1)

The better way is to use divide & conquer, cut n to half from every recursion.
Be careful when n = Integer.MIN_VALUE, if directly set n = -n, it will be wrong due to out of Integer range. So we can do some transformation, let it be x / x^(-(n + 1)), when n < 0.

time:O(logn), space:O(1)
*/

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

}