Page 2 of 2

11827 - Maximum GCD

Posted: Wed Jan 29, 2014 6:59 pm
by KAI10
Hello, i,m getting runtime error for this code. can any body point out the bug please. really need help .....

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
long long GCD(long long a,long long b)
{
    if (a%b==0) return b;
    return GCD(b,a%b);
}

int main()
{
    int T,p;
    scanf("%d", &T);
    T++;
    for (p=0; p<T ;p++){
        char ch,str[1000];
        long long M[105],count=0,j,l,num=0,i,max=0,k;
        gets(str);
        for (i=0;; i++){
            char str1[1000];
            if (str[i]==' ' || str[i]=='\0'){
                l=0;
                for (j=count; j<i; j++) {str1[l] = str[j]; l++;}
                str1[l]='\0';
                M[num] = atoi(str1);
                num++;
                count = i+1;
            }
            if (str[i]=='\0') break;
        }
        for (j=0; j<num; j++){
            for (k=j+1; k<num; k++){
                l = GCD(M[j], M[k]);
                if (l>max) max = l;
            }
        }
        if (p) printf("%lld\n", max);
    }
    return 0;
}


Re: 11827 maximum GCD

Posted: Wed Jan 29, 2014 11:27 pm
by brianfry713
Your code is throwing a divide by 0 (b = 0) on line 6 running the sample input:
if (a%b==0) return b;

Re: 11827 maximum GCD

Posted: Thu Jan 30, 2014 10:25 am
by KAI10
thanks, i got rid of RE. But now i am getting WA :x . please help........

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
long long GCD(long long a,long long b)
{
    if (!b) return a;
    if (!a) return b;
    if (a%b==0) return b;
    return GCD(b,a%b);
}

int main()
{
    int T,p;
    scanf("%d", &T);
    T++;
    for (p=0; p<T ;p++){
        char ch,str[1000];
        long long M[105],count=0,j,l,num=0,i,max=0,k;
        gets(str);
        for (i=0;; i++){
            char str1[1000];
            if (str[i]==' ' || str[i]=='\0'){
                l=0;
                for (j=count; j<i; j++) {str1[l] = str[j]; l++;}
                str1[l]='\0';
                M[num] = atoi(str1);
                num++;
                count = i+1;
            }
            if (str[i]=='\0') break;
        }
        for (j=0; j<num; j++){
            for (k=j+1; k<num; k++){
                l = GCD(M[j], M[k]);
                if (l>max) max = l;
            }
        }
        if (p) printf("%lld\n", max);
    }
    return 0;
}


Re: 11827 maximum GCD

Posted: Thu Jan 30, 2014 10:28 pm
by brianfry713
Doesn't match the sample I/O.

Re: 11827 maximum GCD

Posted: Wed May 14, 2014 8:49 am
by uDebug
Here's some input / output that I found useful during testing / debugging.

Note that the judge's input does not have a case like the 4th one below but I think it makes sense to handle this, so, I threw it in.

Input:

Code: Select all

4
     45      20     30        40 100          10000        1500
  13                20                    93     31         
     0   99          
              0                         
AC Output:

Code: Select all

500
31
99
0

Re: 11827 - Maximum GCD

Posted: Thu Oct 30, 2014 12:20 am
by LazyTym
Why getting WA?????????????i think it's an easy problem bt i can not find the bug...........pls help.......

Code: Select all

#include<iostream>
#include<cstdio>
using namespace std;

int EUCILD(int a,int b) {
    if(b==0) return a;
    else EUCILD(b,a%b);
}

int main()
{
    int A[101];
    int t,a;
    cin>>t;
    while(t--) {
        int i=0,c;
        int p,maximum=0;
        char ch;
        do
        {
            scanf("%d%c",&A[i],&ch);
            i++;
        }
        while(ch==' ');
        c=i--;

        for(int i=0;i<c-1;i++) {
            for(int j=i+1;j<c;j++) {
                if(A[i]<A[j]) {
                   p=EUCILD(A[j],A[i]);
                }
                else {
                   p=EUCILD(A[i],A[j]);
                }
                if(maximum<p) maximum=p;
            }
        }
        cout<<maximum<<endl;
    }
    return 0;
}


Re: 11827 - Maximum GCD

Posted: Thu Oct 30, 2014 9:39 pm
by brianfry713
Your code doesn't work on the sample input. Try parsing the input line by line and then use something like strtok or stringstream to extract the tokens of each line.

Re: 11827 - Maximum GCD

Posted: Tue Dec 09, 2014 3:38 pm
by richatibrewal
Hii,the following code got accepted for 0.015 s. How can I improve this code ?

Code: Select all

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int gcd(int a,int b)
{
    int r;
    while(b!=0)
    {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
int main()
{
    int n,a[200]={0},i,j,max=-1,l,len,flag,g;
    char s[100096];
    scanf("%d",&n);
    getchar();
    while(n--)
    {
        j=-1;
        max=-1;
        flag=1;
        fgets(s,100096,stdin);
        for(i=0;i<=strlen(s)-1;i++)
        {
            if(s[i]==' ')
            {
                flag=1;
                continue;
            }
            if((flag==1)||(i==strlen(s)-1))
            {
                a[++j]=0;
                flag=0;
                for(len=j-2;len>=0;len--)
                {
                    g=gcd(a[j-1],a[len]);
                    if(g>max)
                        max=g;
                }
            }
            if(i<strlen(s)-1)
            {
                l=s[i]-48;
                a[j]=(10*a[j])+l;
            }
        }
        printf("%d\n",max);
    }
    return 0;
}