Given an array of N positive integers, find GCD of all the array elements.
Example 1:
Input: N = 3, arr[] = {2, 4, 6}
Output: 2
Explanation: GCD of 2,4,6 is 2.
Example 2:
Input: N = 1, arr[] = {1}
Output: 1
Explanation: Greatest common divisor of
all the numbers is 1.
Your Task:  
You don't need to read input or print anything. Complete the function gcd()which takes N and array as input parameters and returns the gcd.
Expected Time Complexity: O(N logN)
Expected Auxiliary Space: O(1) 
Constraints:
1 ≤ N, arr[i] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Starter code: #User function Template for python3



class Solution:

    def gcd(self, n, arr):

        # code here 

Solutions:
class Solution:

	def find_gcd(self, a, b):
		if a >= b:
			x = a
			y = b
		else:
			x = b
			y = a
		remainder = y
		while x % y != 0:
			remainder = x % y
			x = y
			y = remainder
		return remainder

	def gcd(self, n, arr):
		result = arr[0]
		for i in range(1, n):
			result = self.find_gcd(result, arr[i])
		return result


class Solution:

	def hcf(self, a, b):
		if b == 0:
			return a
		else:
			return self.hcf(b, a % b)

	def gcd(self, n, arr):
		if n == 1:
			return arr[0]
		else:
			a = arr[0]
			b = arr[1]
			c = self.hcf(a, b)
			for i in range(2, n):
				c = self.hcf(c, arr[i])
			return c


class Solution:

	def gcd(self, n, arr):
		mini = min(arr)
		maxi = max(arr)
		for i in range(mini, 0, -1):
			flg = 1
			for x in arr:
				if x % i != 0:
					flg = 0
					break
			if flg == 1:
				return i


import math as m

class Solution:

	def gcd(self, n, arr):
		if n == 1:
			return arr[0]
		else:
			a = arr[0]
			b = arr[1]
			c = self.hcf(a, b)
			for i in range(2, n):
				c = self.hcf(c, arr[i])
			return c

	def hcf(self, a, b):
		if b == 0:
			return a
		else:
			return self.hcf(b, a % b)


class Solution:

	def gcda(self, a, b):
		while a % b != 0:
			temp = a % b
			a = b
			b = temp
		return b

	def gcd(self, n, arr):
		w = arr[0]
		for i in range(n):
			w = self.gcda(w, arr[i])
		return w


import math

class Solution:

	def gcd(self, n, arr):
		r = arr[0]
		for i in range(1, n):
			r = math.gcd(r, arr[i])
		return r


import functools
import math

class Solution:

	def gcd(self, n, arr):
		p = functools.reduce(math.gcd, arr)
		return p


def gcd2(a, b):
	if b > a:
		(a, b) = (b, a)
	if b == 0:
		return a
	return gcd2(a % b, b)

class Solution:

	def gcd(self, n, arr):
		if n == 1:
			return arr[0]
		g = gcd2(arr[0], arr[1])
		for i in range(2, n):
			g = gcd2(arr[i], g)
		return g


class Solution:

	def gcd(self, n, arr):
		if n < 2:
			return arr[0]
		fsgcd = self.getgcd(arr[0], arr[1])
		if n == 2:
			return fsgcd
		for i in range(2, len(arr)):
			fsgcd = self.getgcd(fsgcd, arr[i])
		return fsgcd

	def getgcd(self, a, b):
		mx = max(a, b)
		mn = min(a, b)
		if mn == 0:
			return mx
		return self.getgcd(mn, mx % mn)


import math

class Solution:

	def gcd(self, n, arr):
		result = 0
		for i in range(n):
			result = math.gcd(result, arr[i])
		return result


import math
from collections import Counter

class Solution:

	def gcd(self, n, arr):
		g = arr[0]
		l = []
		for i in range(1, n):
			g = math.gcd(g, arr[i])
		return g


import math

class Solution:

	def gcd(self, n, arr):
		gcd = arr[0]
		for i in range(1, len(arr)):
			gcd = math.gcd(gcd, arr[i])
			if gcd == 1:
				break
		return gcd


class Solution:

	def gcd(self, n, arr):
		for i in range(min(arr) + 1, 0, -1):
			for j in arr:
				if j % i != 0:
					break
			else:
				return i


class Solution:

	def gcd(self, n, arr):
		m = arr[0]
		for i in range(0, n):
			if m > arr[i]:
				m = arr[i]

		def check(m):
			nonlocal arr
			for i in arr:
				if i % m != 0:
					return False
			return True
		while m > 1:
			if check(m) == True:
				return m
			m -= 1
		return m


class Solution:

	def gcd(self, n, arr):
		if n == 1:
			return arr[0]
		else:

			def gcd_of_two(a, b):
				m = max(a, b)
				n = min(a, b)
				if n == 0:
					return m
				else:
					return gcd_of_two(n, m % n)
			hcf = gcd_of_two(arr[0], arr[1])
			for i in range(2, n):
				hcf = gcd_of_two(hcf, arr[i])
			return hcf


import math

class Solution:

	def gcd(self, n, arr):
		b = arr[0]
		for i in range(1, len(arr)):
			g = math.gcd(b, arr[i])
			b = g
		return b


class Solution:

	def gcd(self, n, arr):
		import math
		if n > 1:
			m = math.gcd(arr[0], arr[1])
			for i in range(2, n):
				m = math.gcd(m, arr[i])
			return m
		else:
			return arr[0]


class Solution:

	def gcd(self, n, arr):

		def gcd(a, b):
			(a, b) = (max(a, b), min(a, b))
			r = a % b
			while r != 0:
				a = b
				b = r
				r = a % b
			return b
		if n == 1:
			return arr[0]
		elif n == 2:
			g = gcd(arr[0], arr[1])
		else:
			g = g = gcd(arr[0], arr[1])
			for i in range(2, n):
				g = gcd(arr[i], g)
		return g


class Solution:

	def gcd(self, n, arr):
		m = min(arr)
		for i in arr:
			if i % m != 0:
				a = i
				b = m
				while b:
					(a, b) = (b, a % b)
				m = a
		return m


class Solution:

	def gcd(self, n, arr):
		x = arr[0]
		index = 1
		while n > 0 and index < n:
			y = arr[index]
			x = gdcOfTwoNum(x, y)
			index += 1
		return x

def gdcOfTwoNum(a, b):
	if b == 0:
		return a
	return gdcOfTwoNum(b, a % b)


class Solution:

	def GCD(self, a, b):
		if b == 0:
			return a
		else:
			return self.GCD(b, a % b)

	def gcd(self, n, arr):
		if n == 1:
			return arr[0]
		else:
			ans = self.GCD(arr[0], arr[1])
			for i in range(2, n):
				ans = self.GCD(ans, arr[i])
		return ans


class Solution:

	def gcd_of_2(self, a, b):
		if b == 0:
			return a
		else:
			return self.gcd_of_2(b, a % b)

	def gcd(self, n, arr):
		if len(arr) > 1:
			gcd = self.gcd_of_2(arr[0], arr[1])
			for i in range(2, len(arr)):
				gcd = self.gcd_of_2(gcd, arr[i])
		else:
			return arr[0]
		return gcd


class Solution:

	def ger(self, x, y):
		while y:
			(x, y) = (y, x % y)
		return x

	def gcd(self, n, arr):
		ans = 1
		if len(arr) == 1:
			return arr[0]
		n1 = arr[0]
		n2 = arr[1]
		ans = self.ger(n1, n2)
		for i in range(2, n):
			ans = self.ger(ans, arr[i])
		return ans


class Solution:

	def gcd_(self, x, y):
		if y == 0:
			return x
		ob = Solution()
		return ob.gcd_(y, x % y)

	def gcd(self, n, arr):
		if n == 1:
			return arr[0]
		ob = Solution()
		g = ob.gcd_(arr[0], arr[1])
		for i in range(2, n):
			g = ob.gcd_(g, arr[i])
		return g


class Solution:

	def gcd(self, n, arr):

		def gcd(a: int, b: int) -> int:
			div = min(a, b)
			while div > 0:
				if a % div == 0 and b % div == 0:
					return div
				else:
					div -= 1
		hcf = arr[0]
		for i in range(1, n):
			hcf = gcd(arr[i], hcf)
		return hcf


class Solution:

	def m(self, a, b):
		if not b:
			return a
		return self.m(b, a % b)

	def gcd(self, n, arr):
		while len(arr) > 1:
			(a, b) = arr[:2]
			del arr[0]
			arr[0] = self.m(a, b)
		return arr[0]


def gcd_eval(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

class Solution:

	def gcd(self, n, arr):
		ans = arr[0]
		for i in range(1, n):
			ans = gcd_eval(arr[i], ans)
			if ans == 1:
				return 1
		return ans


import math

class Solution:

	def gcd(self, n, arr):
		g = 0
		for i in arr:
			g = math.gcd(i, g)
		return g


class Solution:

	def gcd(self, n, arr):

		def calc(num1, num2):
			if num1 == 0:
				return num2
			return calc(num2 % num1, num1)
		arr.sort()
		result = arr[0]
		for i in range(n - 1):
			result = calc(result, arr[i + 1])
		return result


class Solution:

	def gcd(self, n, arr):
		if len(arr) > 1:
			divid = arr[1]
			divisor = arr[0]
			rem = 1
			while rem > 0:
				rem = divid % divisor
				if rem == 0:
					gcd = divisor
				else:
					divid = divisor
					divisor = rem
			if len(arr) > 2:
				for i in arr[2:]:
					if i % gcd == 0:
						pass
					else:
						rem = 1
						divid = i
						divisor = gcd
						while rem > 0:
							rem = divid % divisor
							if rem == 0:
								gcd = divisor
							else:
								divid = divisor
								divisor = rem
			return gcd
		else:
			return arr[0]


class Solution:

	def g(self, a, b):
		r = a % b
		while r != 0:
			a = b
			b = r
			r = a % b
		return b

	def gcd(self, n, arr):
		ans = arr[0]
		for i in range(1, n):
			ans = Solution.g(self, ans, arr[i])
		return ans


class Solution:

	def gcd(self, n, arr):

		def find_gcd(a, b):
			while b:
				(a, b) = (b, a % b)
			return a
		gcd = arr[0]
		for i in range(1, len(arr)):
			gcd = find_gcd(gcd, arr[i])
		return gcd


from fractions import gcd
from functools import reduce

class Solution:

	def gcd(self, n, arr):
		self = reduce(gcd, arr)
		return self


class Solution:

	def hcf(self, x, y):
		maxi = max(x, y)
		mini = min(x, y)
		while mini:
			(maxi, mini) = (mini, maxi % mini)
		return maxi

	def gcd(self, n, arr):
		x = 0
		for i in range(n):
			x = self.hcf(x, arr[i])
		return x


class Solution:

	def gcd(self, n, arr):
		mini = min(arr)
		while mini > 0:
			res = True
			for i in range(n):
				if arr[i] % mini != 0:
					res = False
			if res:
				return mini
			else:
				mini -= 1


class Solution:

	def gcd(self, n, arr):
		max1 = 1
		for i in range(1, min(arr) + 1):
			s = 0
			for j in arr:
				if j % i != 0:
					s = 1
					break
			if s == 0:
				max1 = max(max1, i)
		return max1


class Solution:

	def gcd(self, n, arr):
		num = min(arr)
		checknum = num
		for i in range(1, num + 1):
			checknum = num / i
			flag = 0
			for j in arr:
				if j % checknum != 0:
					flag = 1
					break
			if flag == 0:
				return int(checknum)
		return 1


class Solution:

	def gcd(self, n, arr):

		def gcd_numbers(number_one, number_two):
			if number_one == 0:
				return number_two
			running_gcd = gcd_numbers(number_two % number_one, number_one)
			return running_gcd
		answer = arr[0]
		for i in range(1, len(arr)):
			answer = gcd_numbers(answer, arr[i])
		return answer


class Solution:

	def gcd(self, n, arr):

		def euclid(a, b):
			if a == 0:
				return b
			return euclid(b % a, a)
		ans = 0
		for i in range(n):
			ans = euclid(ans, arr[i])
		return ans


import math

class Solution:

	def gcd(self, n, arr):
		(a, b) = (0, 0)
		if n > 2:
			a = arr[0]
			b = arr[1]
			a = math.gcd(a, b)
			for i in range(2, n):
				b = arr[i]
				a = math.gcd(a, b)
		elif n == 2:
			a = arr[0]
			b = arr[1]
			a = math.gcd(a, b)
		else:
			a = arr[0]
		return a


import math

def find_gcd(p, q):
	return math.gcd(p, q)

class Solution:

	def gcd(self, n, arr):
		if n > 1:
			num1 = arr[0]
			num2 = arr[1]
			gcd = find_gcd(num1, num2)
			for i in range(2, len(arr)):
				gcd = find_gcd(gcd, arr[i])
			return gcd
		return arr[0]


from math import ceil

def gcd_of_2(a: int, b: int):
	(big, small) = (max(a, b), min(a, b))
	while big % small != 0:
		temp = small
		small = big % small
		big = temp
	return small

class Solution:

	def gcd(self, n, arr):
		if n < 2:
			return arr[0]
		elif n == 2:
			return gcd_of_2(arr[0], arr[1])
		else:
			new_arr = [gcd_of_2(arr[i], arr[n - 1 - i]) for i in range(0, (n - 1) // 2 + 1)]
			return self.gcd(ceil(n / 2), new_arr)


class Solution:

	def gcdOfTwo(self, A, B):
		while B:
			(A, B) = (B, A % B)
		return A

	def gcd(self, n, arr):
		if len(arr) == 1:
			return arr[0]
		gcd = self.gcdOfTwo(arr[0], arr[1])
		for i in range(2, len(arr)):
			gcd = self.gcdOfTwo(gcd, arr[i])
		return gcd


from math import gcd as G

class Solution:

	def gcd(self, n, arr):
		lst = []
		for i in range(1, max(arr) + 1):
			for j in arr:
				if j % i != 0:
					break
			else:
				lst.append(i)
		return max(lst)


class Solution:

	def gcd(self, n, arr):
		if n == 1:
			return arr[0]
		elif n == 2:
			return self.cal_gcd(arr[0], arr[1])
		gcd_num = self.cal_gcd(arr[0], arr[1])
		for i in range(2, n):
			gcd_num = self.cal_gcd(arr[i], gcd_num)
		return gcd_num

	def cal_gcd(self, a, b):
		if a == 0:
			return b
		return self.cal_gcd(b % a, a)


class Solution:

	def fun(self, a, b):
		if a == 0:
			return b
		if b == 0:
			return a
		return self.fun(b, a % b)

	def gcd(self, n, arr):
		sum = arr[0]
		for i in range(1, n):
			sum = self.fun(sum, arr[i])
		return sum


class Solution:

	def gcd(self, n, arr):
		from math import gcd
		res = arr[0]
		for i in range(n):
			res = gcd(res, arr[i])
		return res


class Solution:

	def gcd(self, n: int, arr: list) -> int:

		def find_gcd(a: int, b: int) -> int:
			while a:
				(a, b) = (b % a, a)
			return b
		if n == 1:
			return arr[0]
		result = find_gcd(arr[0], arr[1])
		for i in range(2, n):
			result = find_gcd(result, arr[i])
		return result


class Solution:

	def g(self, a, b):
		while a % b != 0:
			rem = a % b
			a = b
			b = rem
		return b

	def gcd(self, n, arr):
		ans = arr[0]
		for i in range(1, n):
			if i == 1:
				ans = self.g(arr[i - 1], arr[i])
			else:
				ans = self.g(ans, arr[i])
		return ans


def hghh(A, B):
	if B == 0:
		return A
	if B > A:
		(A, B) = (B, A)
	return hghh(B, A % B)

class Solution:

	def gcd(self, n, arr):
		if n < 2:
			return arr[n - 1]
		res = hghh(arr[0], arr[1])
		for i in range(1, n):
			res = hghh(res, arr[i])
		return res


class Solution:

	def gcd1(self, a, b):
		while b != 0:
			if a > b:
				(a, b) = (b, a)
			b = b % a
		return a

	def gcd(self, n, arr):
		s = arr[0]
		for i in range(1, n):
			j = self.gcd1(s, arr[i])
			s = j
		return s


class Solution:

	def gcd(self, n, arr):
		res = arr[0]

		def new_gcd(num2, num1):
			if num2 % num1 == 0:
				return num1
			return new_gcd(num1, num2 % num1)
		for ele in arr:
			res = new_gcd(ele, res)
		return res


class Solution:

	def calc_gcd(self, a, b):
		if b == 0:
			return a
		return self.calc_gcd(b, a % b)

	def gcd(self, n, arr):
		gc_d = arr[0]
		for a in arr:
			gc_d = self.calc_gcd(gc_d, a)
		return gc_d


class Solution:

	def gcd(self, n, arr):
		if n == 1:
			return arr[0]
		G = arr[0]
		for i in range(1, n):
			a = G
			b = arr[i]
			while b:
				(a, b) = (b, a % b)
			G = a
		return G


class Solution:

	def gcd(self, n, L):
		if n == 1:
			return L[0]
		(a, b) = (L[0], L[1])
		while b:
			(a, b) = (b, a % b)
		for i in range(2, len(L)):
			b = L[i]
			while b:
				(a, b) = (b, a % b)
		return a


class Solution:

	def gcd(self, n, arr):
		d = min(arr)
		for j in range(d, 0, -1):
			counter = 0
			for k in range(0, n):
				if arr[k] % j == 0:
					counter += 1
			if counter == n:
				return j


import math

class Solution:

	def getgcd(self, x, y):
		return math.gcd(x, y)

	def gcd(self, n, arr):
		if len(arr) == 1:
			return arr[0]
		else:
			initgcd = self.getgcd(arr[0], arr[1])
			for i in range(2, len(arr)):
				initgcd = self.getgcd(initgcd, arr[i])
			return initgcd


import math

class Solution:

	def gcd(self, n, arr):
		if len(arr) == 1:
			return arr[0]
		c = math.gcd(arr[0], arr[1])
		for x in range(2, n):
			c = math.gcd(c, arr[x])
		return c


class Solution:

	def helper(self, a, b):
		while a % b != 0:
			(a, b) = (b, a % b)
		return b

	def gcd(self, n, arr):
		w = arr[0]
		for i in arr:
			w = self.helper(w, i)
		return w


class Solution:

	def ans(self, x, y):
		while y:
			(x, y) = (y, x % y)
		return x

	def gcd(self, n, arr):
		if n == 1:
			return arr[0]
		v1 = arr[0]
		v2 = arr[1]
		res = self.ans(v1, v2)
		for i in range(2, n):
			res = self.ans(res, arr[i])
		return res


class Solution:

	def gcd(self, n, arr):
		gcd = arr[0]
		i = 1
		while i < n:
			gcd = self.gcdAB(gcd, arr[i])
			if gcd == 1:
				return 1
			i = i + 1
		return gcd

	def gcdAB(self, A, B):
		if A < B:
			divisor = A
			dividend = B
		else:
			divisor = B
			dividend = A
		while divisor % dividend != 0:
			remainder = dividend % divisor
			if remainder == 0:
				break
			else:
				dividend = divisor
				divisor = remainder
		return divisor


class Solution:

	def GCD(self, a, b):
		(a, b) = (max(a, b), min(a, b))
		if a % b == 0:
			return b
		return self.GCD(b, a % b)

	def gcd(self, n, arr):
		res = arr[0]
		for i in range(1, n):
			res = self.GCD(res, arr[i])
		return res


class Solution:

	def cal_gcd(self, a, b):
		if b == 0:
			return a
		return self.cal_gcd(b, a % b)

	def gcd(self, n, arr):
		if len(arr) == 1:
			return arr[0]
		num1 = arr[0]
		num2 = arr[1]
		g = self.cal_gcd(num1, num2)
		for i in range(2, len(arr)):
			g = self.cal_gcd(g, arr[i])
		return g