# 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>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/mathematics/greatest-common-divisor-or-highest-common-factor.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.