In short: If the gcd of entire array is 1, then answer is n. Otherwise answer is -1. Proof is given in the editorial.
Finding gcd of entire array could be done like this.
g = a[0];
for (int i = 1; i < n; i++)
g = gcd(g, a[i]);
1 Like
Test cases for this one were weak, my solution got accepted even when it returned -1 for array 2, 6, 3, correct answer is 3…
2 Likes
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.
beautifully different, great question for a cakewalk.
1 Like
For all trouble understanding this is how gcd to 3 numbers is defined, we can extend this to n numbers similarly:
gcd(a,b,c)=gcd(a,(gcd(b,c)).
2 Likes
#include<stdio.h>
long int *arr;
int main()
{
long int i=0,gcd,n,t;
scanf("%ld",&t);
while(t--!=0)
{
scanf("%ld",&n);
arr=malloc(sizeof(long int)*n);
for(i=0;i<n;i++)
scanf("%ld",&arr[i]);
gcd=gcdf(arr[0],arr[1]);
if(n==2)
{
if(gcd==1)
printf("\n%ld",n);
}
else
{
for(i=2;i<n;i++)
{
gcd=gcdf(gcd,arr[i]);
if(gcd==1)
{printf("\n%ld",n);break;}
} }
if(gcd!=1)
printf("-1");
}
//getch();
}
int gcdf(long int a,long int b)
{
long int r;
if(b>a)
return gcdf(b,a);
r=a%b;
if(r==0)
return b;
else
return gcdf(b,r);
}
what is wrong in my code??
Can someone explain the following statement with an example??? “”"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"""
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…
For the entire array the gcd is 1 also. gcd(2, 2, 4, 5, 7) = 1
5 Likes
I am adding a short explanation. Please check if you find it useful.
Btw, Answer of this case will be 3, because gcd(2, 3, 6) = 1.
@dpraveen please next time make your contest without that 502 or 503, it demotivates to code. thanks.
1 Like
for the input 2 3 6
g=2
iteration 1: g = gcd(2,3) = 1
iteration 2: g = gcd(1,6) = 1
answer will be 3 (according to the code)
but the actual answer must be 2
Why? Why the actual answer should be 2?
3 6 will give gcd as 2
there is only 2,3 subarray whose gcd is 1
The subarray [2, 3, 6] has gcd 1, So answer will be 3, why 2?
ohh…
thnks for correcting me 
Mention not