@dwoollley3 …the exact thing i thought 
For all those who misinterpreted it as “GCD of every pair of integers within the subarray had to be 1”, I hope you solved SUBLCM, because that’s what it was.
But this confusion should not have been there, because I had formally defined in next line the meaning clearly that GCD(A_i…A_j) should be 1. There was no mention about pairwise at all.
2 Likes
simply take the gcd of all no’s in the array u will get it
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)).
1 Like
remove if(gc!=1)
#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??
forgot to put new line in printf("-1\n");
1 Like
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"""
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"""
@chari407 If two consecutive elements are co-prime, i.e GCD(a[i],a[i+1]) =1 , then we can add other elements of the array because the commulative GCS will be unity.
you can check this for array of 5 elements: 2 4 5 8 16, since GCD(5,8) =1 , hence GCD of all the elements is one, GCD(2,4,5,8,16)=1, so maximum sub-array which can be chosen is the array itself.
@dwoolley3 If two consecutive elements are co-prime, i.e GCD(a[i],a[i+1]) =1 , then we can add other elements of the array because the commulative GCS will be unity. you can check this for array of 5 elements: 2 4 5 8 16, since GCD(5,8) =1 , hence GCD of all the elements is one, GCD(2,4,5,8,16)=1, so maximum sub-array which can be chosen is the array itself.
@shashaa35 you could have used puts("-1"); As rahul_nexus pointed out there’s no newline after printing -1.
@chari407 If two consecutive elements are co-prime, i.e GCD(a[i],a[i+1]) =1 , then we can add other elements of the array because the commulative GCS will be unity. you can check this for array of 5 elements: 2 4 5 8 16, since GCD(5,8) =1 , hence GCD of all the elements is one, GCD(2,4,5,8,16)=1, so maximum sub-array which can be chosen is the array itself.
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…