The greatest common divisor (GCD), also called highest common factor (HCF) of N numbers is the largest positive integer that divides all numbers without giving a remainder.

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

Input The input to the function/method consists of two arguments - num, an integer representing the number of positive integers (N). arr, a list of positive integers.

Output Return an integer representing the GCD of the given positive integers.

Example Input: num = 5 arr = [2, 4, 6, 8, 10]

Output: 2

Explanation: The largest positive integer that divides all the positive integers 2, 4, 6, 8, 10 without a remainder is 2. So, the output is 2.

Solution

pseudo-code

greatest = -Infinity

for num of arr
  if (num / numArg) > greatest
    set greatest to new value

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