### 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]: http://www.codechef.com/problems/SUBGCD

[2]: http://www.codechef.com/COOK50/problems/SUBGCD

[3]: http://www.codechef.com/users/darkshadows

[4]: http://www.codechef.com/users/rustinpiece

[5]: http://www.codechef.com/users/devuy11

[6]: http://www.codechef.com/download/Solutions/COOK50/Setter/SUBGCD.cpp

[7]: http://www.codechef.com/download/Solutions/COOK50/Tester/SUBGCD.cpp