You are given an array arr of n elements. In one operation you can pick two indices i and j, such that arr[i] >= arr[j] and replace the value of arr[i] with (arr[i] - arr[j]). You have to minimize the values of the array after performing any number of such operations.
Example 1:
Input:
n = 3
arr = {3,2,4}
Output:
1
Explanation:
1st Operation : We can pick 4 & 3, subtract 4-3 => {3,2,1}
2nd Opeartion : We can pick 3 & 2, subtarct 3-2 => {1,2,1}
3rd Operation : We can pick 1 & 2, subtract 2-1 => {1,1,1}
4th Opeartion : We can pick 1 & 1, subtract 1-1 => {1,0,1}
5th Operation : We can pick 1 & 1, subtract 1-1 => {0,0,1}
After this no operation can be performned, so maximum no is left in the array is 1, so the ans is 1.
Example 2:
Input:
n = 2
arr = {2,4}
Output:
2
Explanation:
1st Operation : We can pick 4 & 2, subtract 4-2 => {2,2}
2nd Operation : We can pick 2 & 2, subtract 2-2 => {0,2}
After this no operation can be performned, so maximum no is left in the array is 2, so the ans is 2.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function minimumNumber() which takes an integer n and an array arr, as input parameters and returns the maximum number which is minimized after performing operations.
Expected Time Complexity: O(n)
Expected Space Complexity: O(1)
Constraints:
1 ≤ n ≤ 10^{5}
1 ≤ arr[i] ≤ 10^{9}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Mathematics

Starter code: #User function Template for python3



class Solution:

    def minimumNumber(self, n, arr):

        #code here

Solutions:
class Solution:

	def minimumNumber(self, n, arr):

		def hcf(a, b):
			if b == 0:
				return a
			return hcf(b, a % b)
		if n > 1:
			num = hcf(arr[0], arr[1])
			for i in range(1, n, 1):
				num = hcf(num, arr[i])
			return num
		else:
			return arr[0]


import math

class Solution:

	def minimumNumber(self, n, arr):
		x = min(arr)
		for i in arr:
			x = math.gcd(i, x)
		return x


import math

class Solution:

	def minimumNumber(self, n, arr):
		if len(set(arr)) == 1:
			return arr[0]
		x = min(arr)
		for i in arr:
			x = math.gcd(i, x)
		return x


class Solution:

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

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


class Solution:

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

def gcd(a: int, b: int):
	while True:
		if a == 0:
			return b
		if b == 0:
			return a
		if a >= b:
			[a, b] = [b, a - b]
		else:
			[a, b] = [b - a, a]


import math

class Solution:

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


class Solution:

	def gcd(self, a, b):
		(a, b) = (max(a, b), min(a, b))
		if b == 0:
			return a
		r = a % b
		while r != 0:
			a = b
			b = r
			r = a % b
		return b

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


class Solution:

	def minimumNumber(self, n, arr):

		def gcd(a, b):
			while b % a != 0:
				t = a
				a = b % a
				b = t
			return a
		ans = arr[0]
		for i in range(1, n):
			ans = gcd(ans, arr[i])
		return ans


class Solution:

	def minimumNumber(self, n, arr):

		def find_gcd(x, y):
			while y:
				(x, y) = (y, x % y)
			return x
		num1 = 0
		num2 = arr[0]
		gcd = find_gcd(num1, num2)
		for i in range(1, len(arr)):
			gcd = find_gcd(gcd, arr[i])
		return gcd


class Solution:

	def minimumNumber(self, n, arr):
		if n == 1:
			return arr[0]
		while arr.count(0) != n - 1:
			factor = min((v for v in arr if v != 0))
			if factor == 1:
				return 1
			for i in range(n):
				if i != arr.index(factor):
					arr[i] = arr[i] % factor
					if arr[i] != 0 and arr[i] < factor:
						break
		return max(arr)


class Solution:

	def minimumNumber(self, n, arr):
		ans = arr[0]

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


import math
from math import gcd

class Solution:

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


import math

class Solution:

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


class Solution:

	def minimumNumber(self, n, arr):
		try:
			mina = 999999
			maxa = -999999
			for i in range(n):
				if arr[i] > 0 and mina > arr[i]:
					mina = arr[i]
			for i in range(n):
				if arr[i] > 0 and maxa < arr[i]:
					maxa = arr[i]
			if maxa % mina:
				mina = min(mina, maxa % mina)
			for i in range(n):
				arr[i] %= mina
				if arr[i] < mina and arr[i] > 0:
					mina = arr[i]
			return mina
		except e:
			print(arr, mina)


class Solution:

	def minimumNumber(self, n, arr):
		arr = [element for element in arr if element != 0]
		while len(arr) > 1:
			arr = self.loop(arr)
		return sum(arr)

	def loop(self, arr):
		arr = sorted(list(set(arr)))
		new_arr = [arr[0]]
		for element in arr[1:]:
			res = element % arr[0]
			if res != 0:
				new_arr.append(res)
		return new_arr


class Solution:

	def minimumNumber(self, n, arr):
		(Min, Max) = (999999, -999999)
		for i in arr:
			if i > 0 and i < Min:
				Min = i
		for i in arr:
			if i > 0 and i > Max:
				Max = i
		if Max % Min:
			Min = min(Min, Max % Min)
		for i in arr:
			i %= Min
			if i < Min and i > 0:
				Min = i
		return Min


class Solution:

	def minimumNumber(self, n, arr):
		try:
			(Min, Max) = (999999, -999999)
			for i in arr:
				if i > 0 and i < Min:
					Min = i
			for i in arr:
				if i > 0 and i > Max:
					Max = i
			if Max % Min:
				Min = min(Min, Max % Min)
			for i in arr:
				i %= Min
				if i < Min and i > 0:
					Min = i
			return Min
		except e:
			print(arr, Min)


class Solution:

	def gcd(self, n1, n2):
		if n1 % n2 == 0:
			return n2
		else:
			return self.gcd(n2, n1 % n2)

	def minimumNumber(self, n, arr):
		ans = None
		for i in range(n):
			if arr[i] != 0:
				if ans == None:
					ans = self.gcd(arr[i], arr[i])
				else:
					ans = self.gcd(ans, arr[i])
		return ans


import heapq

class Solution:

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

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


import math

class Solution:

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


from math import gcd

class Solution:

	def minimumNumber(self, n, arr):
		obj = Solution()
		x = arr[0]
		for i in arr:
			x = gcd(x, i)
		return x


import math

class Solution:

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


class Solution:

	def minimumNumber(self, n, arr):
		arr.sort()
		for v in arr:
			if v > 0:
				val = v
				break
		ans = 1
		for div in range(1, val + 1):
			if all([i % div == 0 for i in arr]):
				ans = div
		return ans


class Solution:

	def minimumNumber(self, n, arr):
		m = z = min(arr)
		for i in arr:
			if i % z < m and i % z != 0:
				m = i % z
		return m


class Solution:

	def minimumNumber(self, n, arr):
		m = 99999
		for i in arr:
			if i < m:
				m = i
		for i in arr:
			if i % m != 0:
				return 1
		return m


import math

class Solution:

	def minimumNumber(self, n, arr):
		mini = arr[0]
		for i in arr:
			mini = min(mini, i)
		flag = 0
		ans = 2147483647
		for i in arr:
			if i % mini != 0:
				flag = 1
				ans = min(ans, i % mini)
		if flag == 0:
			return mini
		else:
			return ans


class Solution:

	def minimumNumber(self, n, a):
		m = ans = min(a)
		for x in a:
			if x % m:
				ans = min(ans, x % m)
		return ans


def gcd(a, b):
	return gcd(b, a % b) if b else a

class Solution:

	def minimumNumber(self, n, a):
		g = 0
		for x in a:
			g = gcd(g, x)
		return g


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

class Solution:

	def minimumNumber(self, n, arr):
		cur_gcd = arr[0]
		for i in range(1, len(arr)):
			cur_gcd = gcd(cur_gcd, arr[i])
		return cur_gcd


import sys

class Solution:

	def minimumNumber(self, n, arr):
		min_value = sys.maxsize
		for i in range(n):
			if arr[i] % 2 != 0:
				return 1
			min_value = min(min_value, arr[i])
		return min_value


import math

class Solution:

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

	def calculateGcd(self, a: int, b: int) -> int:
		if b == 0:
			return a
		return self.calculateGcd(b, a % b)


import heapq

class Solution:

	def minimumNumber(self, n, arr):
		seen = set(arr)
		arr = [-i for i in seen]
		heapq.heapify(arr)
		m1 = heapq.heappop(arr)
		while arr and arr[0] != 0:
			m2 = arr[0]
			if m2 == -1:
				return 1
			rem = m1 % m2
			if rem and rem not in seen:
				seen.add(rem)
				m1 = heapq.heapreplace(arr, rem)
			else:
				m1 = heapq.heappop(arr)
		return -m1


class Solution:

	def minimumNumber(self, n, arr):
		for i in range(n):
			if arr[i] % 2 == 1:
				return 1
		return min(arr)


class Solution:

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

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


class Solution:

	def minimumNumber(self, n, arr):
		eve = 0
		sig = 0
		tt = min(arr)
		count = 0
		if max(arr) != min(arr):
			for i in range(n):
				if arr[i] % 2 == 0:
					count += 1
				if arr[i] % tt != 0:
					sig = 1
			if sig == 0:
				return tt
			if count == n:
				return 2
			else:
				return 1
		else:
			return arr[0]


class Solution:

	def minimumNumber(self, n, arr):
		arr.sort()
		odd = 0
		ans = arr[n - 1]
		for i in arr:
			if i % 2 != 0:
				odd += 1
			if i < ans:
				ans = i
		if odd > 0:
			ans = 1
		return ans


class Solution:

	def minimumNumber(self, n, arr):
		mn = min(arr)
		for i in range(n):
			if arr[i] % mn != 0:
				return 1
		return mn


class Solution:

	def minimumNumber(self, n, arr):
		while len(set(arr)) > 1:
			arr = sorted(set(arr))
			arr[-1] = arr[-1] - arr[-2]
		return max(arr)


class Solution:

	def gcd(self, n1, n2):
		if not n2:
			return n1
		return self.gcd(n1, n2 % n1)

	def minimumNumber(self, n, arr):
		for x in arr:
			if x & 1:
				return 1
		res = arr[0]
		for ele in arr[1:]:
			res = self.gcd(res, ele)
		return res


class Solution:

	def minimumNumber(self, n, arr):
		arr = list(set(arr))
		while len(set(arr)) > 1:
			(num1, num2) = sorted(set(arr))[-2:]
			if num1 != num2:
				arr[arr.index(num2)] = num2 - num1
		return max(arr)