There's a question on codechef problem Code is "KSUB" , Tried two very similar code , one works and one gives wrong answer

Viewed 16

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;
}
0 Answers
Related