## 11827 - Maximum GCD

Moderator: Board moderators

KAI10
New poster
Posts: 2
Joined: Thu Dec 05, 2013 5:10 pm

### 11827 - Maximum GCD

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;
}

``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11827 maximum GCD

Your code is throwing a divide by 0 (b = 0) on line 6 running the sample input:
if (a%b==0) return b;
Check input and AC output for thousands of problems on uDebug!

KAI10
New poster
Posts: 2
Joined: Thu Dec 05, 2013 5:10 pm

### Re: 11827 maximum GCD

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;
}

``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11827 maximum GCD

Doesn't match the sample I/O.
Check input and AC output for thousands of problems on uDebug!

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

### Re: 11827 maximum GCD

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
``````
Check input and AC output for over 7,500 problems on uDebug!

LazyTym
New poster
Posts: 31
Joined: Tue Jun 24, 2014 9:10 pm

### Re: 11827 - Maximum GCD

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;
}

``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11827 - Maximum GCD

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.
Check input and AC output for thousands of problems on uDebug!

richatibrewal
New poster
Posts: 49
Joined: Mon Jun 16, 2014 7:40 pm

### Re: 11827 - Maximum GCD

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;
}
``````