SUBGCD - editorial

The subarray [2, 3, 6] has gcd 1, So answer will be 3, why 2?

ohh…
thnks for correcting me :slight_smile:

Mention not :slight_smile:

Okay. I was interpreting it wrongly. The instructions said “GCD of all integers in that subarray is 1”, which I took to mean that the GCD of every pair of integers within the subarray had to be 1. Instead, it means that the GCD of all integers taken together is 1.

3 Likes

Exactly. the question stated that!!!

@dwoollley3 …the exact thing i thought :frowning:

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

remove if(gc!=1)

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"""

@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.

lcaaRn - Online C++0x Compiler & Debugging Tool - Ideone.com. why this code is giving wrong answer ???

https://github.com/rrlinus/array.cpp/blob/master/solution_largest_subarry_with_gcd%20_1_

U will miss few cases