Subarray GCD - SUBGCD Code CHEF Easy Question

Hello Everyone , today we will be discussing an Easy Question of Code Chef .

Here is a link to the PROBLEM

So the problem is pretty straightforward , we need to find the largest contiguous subarray , which has a gcd of one .

So lets solve the problem , so the answer is pretty simple ,
either the whole array has gcd one and the answer is one or there doesnt exist a subarray whose gcd is 1 .

So let us prove this by contradiction , if there exists a contiguous subarray of size i<n ans its gcd is one then this is the minimum answer . Now examine the next number in the array , if the gcd is one then our new answer is i+1 , else if there exists a gcd of both then the gcd of the subarray should also be atleast the gcd of both numbers , hence by contradiction the gcdof subararay of size i<n is also not 1 .
Hence , either the answer is n or it does not exist.


Please look at the code for further understanding .

Here is the C++ code :-

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int t;
    cin>>t;
    while(t--)
    {
        long int n;
        scanf("%ld",&n);
        long int arr[n];
        long int gcd,i;
        i=0;
        while(i!=n)
        {
            scanf("%ld",&arr[i]);
            i++;
        }
        gcd=arr[0];
        i=1;
        while(i!=n)
        {
            gcd=__gcd(gcd,arr[i]);
            i++;
        }
        if(gcd==1)
        {
            printf("%ld\n",n);
        }
        else
        {
            printf("-1\n");
        }
    }
// your code goes here
return 0;
}

Please leave any doubts in the comments section .