Poison

1979. Find Greatest Common Divisor of Array

发表于
Recursion
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int findGCD(int[] nums) {
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for (int num : nums) {
            min = Math.min(min, num);
            max = Math.max(max, num);
        }

        return gcd(max, min);
    }

    private int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }

        return gcd(b, a % b);
    }
}
Iterate
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int findGCD(int[] nums) {
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for (int num : nums) {
            min = Math.min(min, num);
            max = Math.max(max, num);
        }

        while (min != 0) {
            int x = max % min;
            max = min;
            min = x;
        }

        return max;
    }
}
Reference

1979. Find Greatest Common Divisor of Array
辗转相除法 - 维基百科，自由的百科全书