Given an array with n elements. Find length of the largest sub-array having GCD equal to 1. If no such  subarray exist with GCD 1, return -1.
Example 1:
Input: n = 3, arr = [1, 3, 5]
Output: 3 
Explanation: GCD of 1, 3 and 5
is equal to 1.So the length is 3. 
Example 2:
Input: n = 3, arr = [2, 4, 6]
Output: -1
Explanation: No such  subarray exist.
Your Task:  
You dont need to read input or print anything. Complete the function findLargestSubarray() which takes array arr of length n as input parameter and returns the length of the largest subarray and if no such subarray exist
returns -1. 
Expected Time Complexity: O(nlogn)
Expected Auxiliary Space: O(1)
Constraints:
1<= n <=1000
1<= arr[i] <=1000

Source: geeksforgeeks | Difficulty: EASY

Starter code: #User function Template for python3

class Solution:

    def findLargestSubarray(self, arr, n):

        # code here

Solutions:
import math

class Solution:

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


class Solution:

	def findLargestSubarray(self, arr, n):

		def gcd(a, b):
			if a == 0:
				return b
			return gcd(b % a, a)
		x = arr[0]
		for i in arr[1:]:
			x = gcd(i, x)
		if x == 1:
			return n
		return -1


class Solution:

	def gcd(self, a, b):
		while b:
			(a, b) = (b, a % b)
		return a

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


import math

class Solution:

	def findLargestSubarray(self, arr, n):
		gcd = arr[0]
		for i in range(1, n):
			gcd = math.gcd(gcd, arr[i])
		return n if gcd == 1 else -1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = input().split()
		for itr in range(n):
			arr[itr] = int(arr[itr])
		ob = Solution()
		print(ob.findLargestSubarray(arr, n))


import math as m

class Solution:

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


class Solution:

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


class Solution:

	def findLargestSubarray(self, arr, n):
		import math
		if len(arr) == 1:
			a = arr[0]
		else:
			a = math.gcd(arr[0], arr[1])
			i = 2
			while i < n:
				a = math.gcd(a, arr[i])
				i += 1
		if a == 1:
			return len(arr)
		else:
			return -1