## 11827 - Maximum GCD

Moderator: Board moderators

Martuza_cseiu
New poster
Posts: 2
Joined: Mon Mar 28, 2011 5:49 am

### 11827

At last I got AC...........

MAMU
New poster
Posts: 6
Joined: Fri Apr 01, 2011 12:45 pm

### 11827 - Maximum GCD (Why RE??)

Code: Select all

``AC``
Last edited by MAMU on Mon Jul 11, 2011 7:28 pm, edited 1 time in total.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### Re: 11827 - Maximum GCD (Why RE??)

As the memory for local variables is allocated in stack, you can't declare such a huge array inside a function.
Try allocating the memory in heap using the new operator or make the array global.

MAMU
New poster
Posts: 6
Joined: Fri Apr 01, 2011 12:45 pm

### Re: 11827 - Maximum GCD (RE again)

Code: Select all

``AC``
Last edited by MAMU on Mon Jul 11, 2011 7:30 pm, edited 1 time in total.

MAMU
New poster
Posts: 6
Joined: Fri Apr 01, 2011 12:45 pm

### Re: 11827 - Maximum GCD (Why RE??)

plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

### Re: 11827 - Maximum GCD (Why RE??)

I got 3 Runtime Errors before I finally got AC so here are some reasons you can get Runtime error.

1. Your Array size is not big enough (100000 is enough).
2. The judge data contains inputs with 0. My first approach was to find the minimum and maximum of the two numbers. So then I check if max % min == 0 then the GCD equals the lesser number. If not then I apply brute force to calculate the GCD. The reason I got runtime error was min can be 0 So make sure your program can handle cases like 0 1 2 3 etc.
3. Try this input:
1
10 20 30 40(space)(space)(space)
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

### Re: 11827 - Maximum GCD (Why RE??)

Mamu I checked your program...your code doesn't output anything for my test case.
1
10 20 30 40(space)(space)(space).
Hope it helps you.
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

MAMU
New poster
Posts: 6
Joined: Fri Apr 01, 2011 12:45 pm

### Re: 11827 - Maximum GCD (Why RE??)

Sorry, I'd got AC before I saw your post but I forgot to remove the post.
plamplam, I think my problem was getting the numbers from the input string.

mathgirl
New poster
Posts: 36
Joined: Tue Apr 24, 2012 6:20 pm

### Re: 11827 - Maximum GCD (Why RE??)

I m constantly getting TLE on this one. Any better algo ?

Code: Select all

``````#include<vector>
#include<stdio.h>
#include<iostream>
#include<limits.h>

using namespace std;

int main()
{
int t,re;
re = scanf("%d",&t);
while(t--)
{
int a,lowest = INT_MAX;
vector<int> input;
getchar();
while(cin.peek() != '\n')
{
re = scanf("%d",&a);
input.push_back(a);
lowest = min(lowest,a);
}

bool valid = true;
for(lowest;lowest >= 2;lowest--)
{
valid = true;
for(int i = 0;i < input.size();i++)
{
if(input[i] % lowest != 0)
{
valid = false;
break;
}
}

if(valid)
break;
}

printf("%d\n",lowest);
}
return 0;
}
``````

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

### Re: 11827 - Maximum GCD (Why RE??)

Doesn't match the sample I/O.

Don't use getchar() and count on it to read a newline. Instead write something like:
while(getchar()!='\n');

Your code goes into an infinite loop if there are trailing spaces on a line.
Check input and AC output for thousands of problems on uDebug!

sornaCse
New poster
Posts: 6
Joined: Thu Jul 26, 2012 9:40 am

### 11827 Why WA?

Code: Select all

``````thank you sir! i got rank 57 with 0.004s :D
``````
Last edited by sornaCse on Fri Jul 27, 2012 8:37 am, edited 1 time in total.

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

### Re: 11827 Why WA?

Reset flag at the beginning of numbers()
Check input and AC output for thousands of problems on uDebug!

raihan004
New poster
Posts: 2
Joined: Tue Oct 09, 2012 2:07 am

### 11827 - Maximum GCD Getting Wrong Ans Need Help

hi am (11827 - Maximum GCD) Getting Wrong Ans Need Help. I dont know where is my fault. pls me help me to find my fault.
here is my code

Code: Select all

``````#include<stdio.h>
int main()
{
int s,t;
scanf("%d",&t);
for(s=0;s<t;s++)
{
long long max=0,a[1000000],n,p,q;
int i,j,m;
char c;
m=0;
do
{
scanf("%lld%c",&a[m],&c);
m++;
}
while(c==' ');
for(i=0;i<m;i++)
{
for(j=i+1;j<m;j++)
{
p=a[i];
q=a[j];
while(q!=0)
{
n=p%q;
p=q;
q=n;
}
if(max<=p)
max=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 Getting Wrong Ans Need Help

Your code doesn't match the sample I/O when I tested it. Try reading the input a line at a time.
Check input and AC output for thousands of problems on uDebug!

shuvokr
Learning poster
Posts: 66
Joined: Tue Oct 02, 2012 8:16 pm
``````AC ...
``enjoying life ..... ``