# Greatest Common Divisor or Highest Common Factor

`Math`

Write an algorithm to determine the GCD of N positive numbers.

## Analysis & Solution

### 欧几里得算法求最大公约数

关于GCD算法，自然是有欧几里得算法Euclid Algorithm。不过实现上，可以是迭代，或者递归。

**Pseudo Code:**

Iterative

```
function gcd(a, b)
    while b ≠ 0
        t ← b
        b ← a mod b
        a ← t
    return a
```

Recursive:

```
function gcd(a, b)
    if b = 0
       return a
    else
       return gcd(b, a mod b)
```

### Iterative (Java)

```java
int gcd(int a, int b) {
        int tmp;
        while (b > 0) {
            tmp = b;
            b = a % b;
            a = tmp;
        }
        return a;
    }
```

### Recursive (Java)

```java
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}
```

### Euclid Algorithm Time Complexity

这是一个挺复杂的数学问题，作为估计（也是实际上的），可以认为迭代次数O(logN)

### 如何从两个数的GCD拓展到N个数呢？

You could use this common property of a GCD:

```
GCD(a, b, c) = GCD(a, GCD(b, c)) = GCD(GCD(a, b), c) = GCD(GCD(a, c), b)
```

GeeksforGeeks:

```java
gcd(a, b, c) = gcd(a, gcd(b, c)) 
             = gcd(gcd(a, b), c) 
             = gcd(gcd(a, c), b)
```

For an array of elements:

```java
result = arr[0]
For i = 1 to n-1
   result = GCD(result, arr[i])
```

### Implementation:

```java
class GCD
{
    private int gcd(int a, int b) {
        int tmp;
        while (b > 0) {
            tmp = b;
            b = a % b;
            a = tmp;
        }
        return a;
    }

    public int generalizedGCD(int num, int[] arr)
    {
        // WRITE YOUR CODE HERE
        if (num == 0 || arr == null) {
            return 0;
        } 
        if (num < 2) {
            return arr[0];
        }
        int ans = arr[0];
        for (int i = 1; i < num; i++) {
            ans = gcd(ans, arr[i]);
        }
        return ans;
    }

}
```

## Reference

Greatest Common Divisor of a list of numbers - C++ and Python Implementation <https://www.rookieslab.com/posts/cpp-python-code-to-find-gcd-of-a-list-of-numbers>

<https://www.geeksforgeeks.org/gcd-two-array-numbers/>

Time complexity of Euclid's Algorithm <https://stackoverflow.com/questions/3980416/time-complexity-of-euclids-algorithm>

欧几里得算法时间复杂度简单分析 <https://blog.csdn.net/ZeroOnet/article/details/53375313>