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.
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 ]
gc = (i==1)?Input:gcd(gc , Input)
if ( gc == 1) print N
else print -1
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.