## 10407 - Simple division

Moderator: Board moderators

yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am

### 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<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
New poster
Posts: 15
Joined: Sun Dec 15, 2002 2:51 pm
How do you solve this? I don't get it

yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am
Thanks for your reply. I got it accepted after recoding it. My algorithm was wrong here. Thanks again.

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
actually yahoo,
your method donot work for repeated input. try it.
--anupam
"Everything should be made simple, but not always simpler"

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
again,
there may be problem about the array size.
check it.
--thanks.
"Everything should be made simple, but not always simpler"

b3yours3lf
New poster
Posts: 44
Joined: Wed Aug 14, 2002 3:02 am

### 10407-Simple Division

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

saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Contact:
i used int for this problem.

-sohel

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

### 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)?
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

makbet
New poster
Posts: 44
Joined: Tue Nov 26, 2002 11:01 pm
Location: Wejherowo
It's very easy, once you know it :
if a mod d = b mod d <=> d divides (a-b). Now the problem gets simple

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
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??
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:
why do you consider the minimum one only?
the most important point here is that d divides ALL pairwise-differences.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
cytse wrote: 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.
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

makbet
New poster
Posts: 44
Joined: Tue Nov 26, 2002 11:01 pm
Location: Wejherowo
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.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
Oh~~~
I get it, thanks a lot!
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

### 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(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.