10407 - Simple division

[yahoo]

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<n-1;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<n-1;i++)
b[i]=a[i+1]-a[i];
lo=b[0];
for(i=1;i<n-1;i++)
if(b[i]<lo)
lo=b[i];
hi=b[0];
for(i=1;i<n-1;i++)
if(b[i]>hi)
hi=b[i];
int gcd=b[0];
for(i=1;i<n-1;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:

[abc]

How do you solve this? I don't get it

[yahoo]

Thanks for your reply. I got it accepted after recoding it. My algorithm was wrong here. Thanks again.

[anupam]

actually yahoo,
your method donot work for repeated input. try it.
--anupam

[anupam]

again,
there may be problem about the array size.
check it.
--thanks.

[b3yours3lf]

I always get TLE.
Can I use long int for this problem or I must use string?

[saiqbal]

i used int for this problem.

-sohel

[..]

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)?

[makbet]

It's very easy, once you know it :
if a mod d = b mod d <=> d divides (a-b). Now the problem gets simple

[..]

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??

[cytse]

why do you consider the minimum one only?
the most important point here is that d divides ALL pairwise-differences.

[..]

the most important point here is that d divides ALL pairwise-differences.

As you say, d divideds ALL pairwise-difference, so d is a factor of any pairwise-difference. Then d is also a factor of the min. pairwise-difference, so d <= min. pairwise-difference. It is safe to only consider the factors of min. pairwise difference.

[makbet]

I don't know what you guys are talking about: you calculate differences of consecutive numbers and then calculate gcd of those. For examle:
17 5 9 3 99 55
differences:
12 4 6 96 44
nwd of those: 2, which is the correct anwser.

[..]

Oh~~~
I get it, thanks a lot!

[Riyad]

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(a-b),abs(b-c),abs(c-d),abs(d-e),........... 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