# DECOGCD - Editorial

Author: Ritesh Gupta
Editorialist: Ritesh Gupta

SIMPLE

# PROBLEM:

You are given a sequence A_1, A_2, \ldots, A_N. You have to split the array into a maximum number of non-empty subarrays such that the gcd of elements of each subarray is equal to 1. If there is no split possible then print ā-1ā.

# Constraints:

• 1 \le T \le 3
• 1 \le N \le 5 \cdot 10^5
• 1 \le A_i \le 10^6 for each valid i

# EXPLANATION:

We can approach this problem greedily. We can perform follow the following steps:

• Initially, the answer is zero.
• Find the smallest length prefix of the current sequence such that gcd of elements is 1.
• Increment the answer by 1 and remove the prefix from the current sequence.
• Repeat step 2 unless the sequence is vanished or have gcd greater than 1.

As every time, we are choosing the best cut possible so the overall answer is optimum possible. One way to prove this is by contradiction. I left this for you.

# SOLUTIONS:

Setter's Solution

#include <bits/stdc++.h>

#define int long long
#define endl ā\nā
#define mod 1000000007

using namespace std;

int32_t main()
{
int t;
cin >> t;

while(t--)
{
int n;
cin >> n;

vector <int> v;

for(int i=0;i<n;i++)
{
int x;
cin >> x;

v.push_back(x);
}

reverse(v.begin(),v.end());

int curr = 0;
int ans = 0;

for(int i=0;i<n;i++)
{
curr = __gcd(curr, v[i]);

if(curr == 1)
{
ans++;
curr = 0;
}
}

if(ans == 0)
cout << -1 << endl;
else
cout << ans << endl;
}


}

Tester's Solution

#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;
using ll=long long;

ll gcd(ll a,ll b)
{
if(a<b)
swap(a,b);

if(!b)
return a;

return gcd(b,a%b);


}

int main()
{
int n,t;
cin>>t;

while(t--)
{
cin>>n;

vector<int> v(n);
for(int i=0;i<n;i++)
{
cin>>v[i];
}

int ans=0,ref=0;
for(int i=0;i<n;i++)
{
ref=gcd(ref,v[i]);

if(ref==1)
{
ans++;
ref=0;
}
}

if(ans)
cout<<ans<<endl;
else
cout<<-1<<endl;
}


}

1 Like

Your editorials are great !!! Thanks