the question is https://www.codechef.com/submit/KSUB?tab=statement , I tried two solutions almost same logic one works and one doesn't . Tweaked the code that deoesn't run but hard to figure out what's wrong . Here are my two solutions the one that works https://www.codechef.com/viewsolution/74694775 the one that doesn't https://www.codechef.com/viewsolution/74695179
My logic
- GCD of all the numbers is smallest possible gcd between any two numbers in the array
- we'll find maximum number of sub array possible with gcd equal to that of the main array
- if the number of sub array with gcd equal to that of the main array exceeds or is equal to the provided partition in the question then output is yes else no
i just want to understand if there is any major difference in both codes which is causing this.
the one that worked
#include <bits/stdc++.h>
using namespace std;
int main() {
int tests;
cin>>tests;
while(tests--){
int n,k,count=0;
cin>>n>>k;
int a[n];
//taking input in array
for(int i=0;i<n;i++){
cin>>a[i];
}
int total=a[0];
//total gcd
for(int i=1;i<n;i++){
total=__gcd(total,a[i]);
}
int i=0;
int curr=a[0];
//counting number of possible partitions
for( i=0;i<n;i++){
curr=__gcd(curr,a[i]);
if(curr==total){
count++;
curr=a[i+1];
}
}
if(count>=k) cout<<"YES\n";
else cout<<"NO\n";
}
return 0;
}
the one that didn't work
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int main() {
int T,n,k,a[200000],i,j,count,gcd,gcd_temp,sum_gcd,flag=0;
cin>>T;
for(;T>0;T--){
cin>>n;
cin>>k;
count=0;
flag=0;
//taking input in array
for(i=0;i<n;i++){
cin>>a[i];
}
gcd=__gcd(a[0],a[1]);
//calculating total gcd
for(i=2;i<n;i++){
gcd==__gcd(gcd,a[i]);
}
gcd_temp=a[0];
//counting number of possible partition
for(i=0;i<n;i++){
gcd_temp=__gcd(gcd_temp,a[i]);
if(gcd==gcd_temp){
count++;
gcd_temp=a[i+1];
}
}
if(count>=k ){
cout<<"YES"<<endl;
}
else{
cout<<"NO"<<endl;
}
}
return 0;
}