SS2 - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest

Author: Sandeep Singh
Tester: Soham Chakraborty
Editorialist: Sandeep SIngh

DIFFICULTY:

SIMPLE

PREREQUISITES:

GCD

PROBLEM:

Given an array A of length N, you have to find if there is any contiguous subarray of A with gcd 1

QUICK EXPLANATION:

Find the gcd of the whole array, if gcd is 1 then such a subarray exists else not.

EXPLANATION:

Let us assume there is a subarray S of the given array A such that gcd of S =1. Now let as add an element K to this subarray. The gcd of the new subarray will be the gcd of S and K. Since gcd of S is 1, the new gcd will also be 1. This stands true no matter how many numbers we add to the subarray S.

Thus, we can conclude that the gcd of an array which has a subarray of gcd 1 is also 1. Conversely, if the gcd of the whole array is 1, there is at least 1 subarray with gcd 1. Hence, we solve the question by finding the gcd of the whole array.
Below is the code for finding the gcd of the array A.

G=0;
for(i=1;i<=N;i++)
	  G=gcd(G,arr[i]);

Time complexity is O(N*C) where C is for calculating gcd.

SOLUTIONS:

Setter's Solution 

#include <bits/stdc++.h>
#define ll long long int
#define Mod 1000000007
using namespace std;
int gcd(int a, int b) 
{ 
    if (a == 0) 
        return b; 
    return gcd(b % a, a); 
} 
void solve(){
	int N,i,G=0,temp;
	cin>>N;
	for(i=0;i<N;i++){
	  cin>>temp;
	  G=gcd(G,temp);
	}
	if(G==1)	
		cout<<"YES"<<endl;
	else
		cout<<"NO"<<endl;
	
}
int main() {
 
	//freopen("ip6.in", "r", stdin);
	//freopen("op6.out", "w", stdout);
 
	int T ;
	cin>>T;
	while(T--)
		solve();
	return 0;
}
Tester's Solution 
#include<bits/stdc++.h>
#define int long long
#define rep(i,j,k)for(int i=j;i<k;i++)
using namespace std;
int n,q;
 
int32_t main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  //freopen("cake_input_file_A.txt", "r", stdin);
  //freopen("cake_output_file_A.txt", "w", stdout);
  int t;
  cin>>t;
  while(t--){ 
    cin >> n;
    vector<int> v(n);
    rep(i,0,n)cin>>v[i];
    int x = v[0],fl=0;
    if(x == 1){
      cout << "YES\n";
      continue;
    }
    rep(i,1,n){
      if(v[i] == 1){
        fl=1;break;
      }
      x = __gcd(x,v[i]);
    }
    if(fl)cout<<"YES";
    else if(x==1)cout<<"YES";
    else cout<<"NO";
    cout << "\n";
  }
  return 0;
}
1 Like