SUBGCD - editorial

editorial
, , ,
1

PROBLEM LINK:

[Practice][1]
[Contest][2]
Author: [Lalit Kundu][3]
Tester: [Tasnim Imran Sunny][4]
Editorialist: [Devendra Agarwal][5]

DIFFICULTY:

CakeWalk

PREREQUISITES:

math

PROBLEM:

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.

Solution:

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 ]

Pseudo Code


	for(int i=1;i<=N;i++){
		Read(Input) 
		gc = (i==1)?Input:gcd(gc , Input)  
	if ( gc == 1) print N
	else print -1

AUTHOR’S and TESTER’S SOLUTIONS:

[Author’s solution][6]
[Tester’s solution][7]
[1]: SUBGCD Problem - CodeChef
[2]: CodeChef: Practical coding for everyone
[3]: darkshadows | CodeChef User Profile for Lalit Kundu | CodeChef
[4]: rustinpiece | CodeChef User Profile for Tasnim Imran Sunny | CodeChef
[5]: devuy11 | CodeChef User Profile for Devendra Agarwal | CodeChef
[6]: http://www.codechef.com/download/Solutions/COOK50/Setter/SUBGCD.cpp
[7]: http://www.codechef.com/download/Solutions/COOK50/Tester/SUBGCD.cpp

13 Likes
2

Can someone explain why the largest subarray has to be the entire array?
Using the following example input:

1
5
2 2 4 5 7

Why wouldn’t the answer be 3 since {4,5,7} is the largest contiguous subset whose members have a GCD of 1?

5 Likes
3

**if the input is given as: 2 3 6

GCD: of 2 and 3 will be 1

GCD: of 1 and 6 will be again 1
**
the answer in this case will be 3

but it should be 2 as only the pair of 2,3 will have GCD 1 and 3,6 will be giving GCD = 2
but after reading the Tester Solution as well, still, I am having this doubt.

please correct me if I am wrong anywhere.

4

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
5

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
6

There’s something wrong with the judge, I can’t see how this code gives WA.

7

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.

8

beautifully different, great question for a cakewalk.

1 Like
9

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
10

SOLUTION I dont know is it really wrong or not? Whatz wrong with it?

11

#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??

12

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

13

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…

14

For the entire array the gcd is 1 also. gcd(2, 2, 4, 5, 7) = 1

5 Likes
15

I am adding a short explanation. Please check if you find it useful.

16

Btw, Answer of this case will be 3, because gcd(2, 3, 6) = 1.

17

@dpraveen please next time make your contest without that 502 or 503, it demotivates to code. thanks.

1 Like
18

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

19

Why? Why the actual answer should be 2?

20

3 6 will give gcd as 2

there is only 2,3 subarray whose gcd is 1