GCD

Part 1： 两个数的最大公约数

Greatest Common Divisor

How to compute GCD? (辗转相除法)

if b == 0, then a is result
else keep doing (a, a % b)
until b reaches 0

Method 1: not recursive
public int findGCD(int a, int b) {
    while (b != 0) {
        int tmp = a;
        a = b;
        b = tmp % b;
    }
    return a; // if b == 0, return a
}

Method 2: recursive
public int findGCD(int a, int b) {
    if (b == 0) return a;
    return findGCD(b, a % b);
}

Part 2: 一个数组的最大公约数

    // just scan the array and update the gcd each time
    public static int findGCDofArray(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int gcd = nums[0];
        for (int num: nums) {
            gcd = findGCD(gcd, num);
        }
        return gcd;
    }