10407  Simple division
Moderator: Board moderators
10407  Simple division
I can't understand why my this code got runtime error. Can anyobody explain where i am doing wrong.Here is my code:
#include<stdio.h>
#define N 3000
main()
{
int tmp,a[N],i,j,r,hi,lo,n,m,b[N];
while(1)
{
n=0;
while(1)
{
scanf("%d",&a[n]);
if(a[n]==0) break;
n++;
}
if(!n) break;
for(i=0;i<n1;i++)
{
m=i;
for(j=i+1;j<n;j++)
if(a[m]>a[j])
m=j;
tmp=a[m];
a[m]=a[i];
a[i]=tmp;
}
for(i=0;i<n1;i++)
b[i]=a[i+1]a[i];
lo=b[0];
for(i=1;i<n1;i++)
if(b[i]<lo)
lo=b[i];
hi=b[0];
for(i=1;i<n1;i++)
if(b[i]>hi)
hi=b[i];
int gcd=b[0];
for(i=1;i<n1;i++)
{
if(b[i]>gcd) { hi=b[i];lo=gcd;}
else{hi=gcd;lo=b[i];}
while (1)
{
r = hi%lo;
if (r!=0)
{
hi = lo;
lo = r;
}
else {gcd=lo;break;}
}
}
printf("%d\n",lo);
}
return 0;
}
:oops:
#include<stdio.h>
#define N 3000
main()
{
int tmp,a[N],i,j,r,hi,lo,n,m,b[N];
while(1)
{
n=0;
while(1)
{
scanf("%d",&a[n]);
if(a[n]==0) break;
n++;
}
if(!n) break;
for(i=0;i<n1;i++)
{
m=i;
for(j=i+1;j<n;j++)
if(a[m]>a[j])
m=j;
tmp=a[m];
a[m]=a[i];
a[i]=tmp;
}
for(i=0;i<n1;i++)
b[i]=a[i+1]a[i];
lo=b[0];
for(i=1;i<n1;i++)
if(b[i]<lo)
lo=b[i];
hi=b[0];
for(i=1;i<n1;i++)
if(b[i]>hi)
hi=b[i];
int gcd=b[0];
for(i=1;i<n1;i++)
{
if(b[i]>gcd) { hi=b[i];lo=gcd;}
else{hi=gcd;lo=b[i];}
while (1)
{
r = hi%lo;
if (r!=0)
{
hi = lo;
lo = r;
}
else {gcd=lo;break;}
}
}
printf("%d\n",lo);
}
return 0;
}
:oops:

 New poster
 Posts: 44
 Joined: Wed Aug 14, 2002 3:02 am
10407Simple Division
I always get TLE.
Can I use long int for this problem or I must use string?
Can I use long int for this problem or I must use string?
10407
I solved it by 0.082s, but I see there are many solutions of 0.002s.
Now I solve it by finding some possible values of d, and then test each value for d.....Is there some way to solve it in O(nlgn) or even O(n)?
Now I solve it by finding some possible values of d, and then test each value for d.....Is there some way to solve it in O(nlgn) or even O(n)?
My signature:
 Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.  I HATE testing account.
 Don't send me source code for debug.
Yes, I know that,
so what I do is, find the minimum (but positive) pairwise difference (diff), then test each factor of diff to check if all the input values get the same remainder r.
But it is slower than others, what do I miss??
so what I do is, find the minimum (but positive) pairwise difference (diff), then test each factor of diff to check if all the input values get the same remainder r.
But it is slower than others, what do I miss??
My signature:
 Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.  I HATE testing account.
 Don't send me source code for debug.
As you say, d divideds ALL pairwisedifference, so d is a factor of any pairwisedifference. Then d is also a factor of the min. pairwisedifference, so d <= min. pairwisedifference. It is safe to only consider the factors of min. pairwise difference.cytse wrote: the most important point here is that d divides ALL pairwisedifferences.
My signature:
 Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.  I HATE testing account.
 Don't send me source code for debug.
10407,WA why ?????????????????
Hi,
My Algorithm is very simple for this problem . i calculated the differences between all the successive numbers and stored them in an array of integer . than calculated the GCD of all the number . which should be the answer.
lets take an example , the sequence of number be
a b c d e f g h i j
i calculated abs(ab),abs(bc),abs(cd),abs(de),........... and stored them in an array .
than i calculated the GCD s of them like this ..
a= it is the int array where i stored the diffences
x=GCD(a[0],a[1])
for(i=2;i<index;i++){
x=GCD(x,a);
}
x is the ans .
What is wrong with my algorithm and code .
plizzzzzzzzzz help.
Riyad
My Algorithm is very simple for this problem . i calculated the differences between all the successive numbers and stored them in an array of integer . than calculated the GCD of all the number . which should be the answer.
lets take an example , the sequence of number be
a b c d e f g h i j
i calculated abs(ab),abs(bc),abs(cd),abs(de),........... and stored them in an array .
than i calculated the GCD s of them like this ..
a= it is the int array where i stored the diffences
x=GCD(a[0],a[1])
for(i=2;i<index;i++){
x=GCD(x,a);
}
x is the ans .
What is wrong with my algorithm and code .
plizzzzzzzzzz help.
Riyad
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN