Given an array A_1,A_2…A_N you have to print the size of the largest contiguous subarray such that GCD of all integers in that subarray is 1. Minimum size of the subarray is 2.

Solution:

Suppose gcd of a subarray is 1. Let us denote this subarray by S.

What is the gcd of this S and any other number ?

It is 1 . Reason : gcd of Subarray is 1 , and gcd(1,any_number) = 1

So , if there is a subarray whose gcd is 1, then any subarray containing this subarray will also have gcd 1.

What is the largest subarray in the whole array?

Full Array itself(i.e subarry of N elements)! If the gcd of all the array elements is 1 ,then answer is N.

Can you prove that if gcd of all the array elements is not 1, then answer is -1.

If gcd of all elements of all array elements is not 1 then it implies that there are no subarrays whose gcd is 1.[ You can prove by contradiction , Important point is that full array will contain all subarray’s ]

Pseudo Code

for(int i=1;i<=N;i++){
Read(Input)
gc = (i==1)?Input:gcd(gc , Input)
if ( gc == 1) print N
else print -1

GCD: of 1 and 6 will be again 1
**
the answer in this case will be 3

but it should be 2 as only the pair of 2,3 will have GCD 1 and 3,6 will be giving GCD = 2
but after reading the Tester Solution as well, still, I am having this doubt.

In the tester solution -
The comparisons inside the assert function for “t” and “n” are not correct. t has been compared with maxn whereas n has been compared with maxt, which can’t be right because t can go to 10 but maxn is 10000 and n can go to 10000 but maxt is 10 only.

Why can’t we just check whether odd and even numbers exists simultaneously or not? I mean there is no pair of odd and even numbers that would give gcd other than 1… correct me if i am wrong…