@Akshata, Satyam: I think that might be because the way you are using to calculate gcd is inefficient.
I got AC. I used the following technique to calculate gcd: long long int gcd(long long int a, long long int b){ long long int rem = a%b; if(rem == 0) return b; return gcd(b,rem); } long long int gcdvar = a[1]-a[0]; for(i=2;i<n;i++) { gcdvar = gcd(a[i]-a[0],gcdvar); } Thanks, Balaji. On Sat, Mar 12, 2011 at 7:16 PM, Akshata Sharma <akshatasharm...@gmail.com>wrote: > > @Balaji: > that WA was due to using int in place of long long in loop. But still, this > is giving TLE. > > On Sat, Mar 12, 2011 at 7:07 PM, Akshata Sharma <akshatasharm...@gmail.com > > wrote: > >> sorry, @satyam: then what is the 'best' solution for this? :) >> >> >> On Sat, Mar 12, 2011 at 7:06 PM, Akshata Sharma < >> akshatasharm...@gmail.com> wrote: >> >>> @Ankur: then what is the 'best' solution for this? :) >>> @Balaji: i tried implementing but I dont know which case it fails?? >>> getting WA now!! >>> Here is the code: >>> >>> #include<stdio.h> >>> >>> int main() >>> { >>> long n,gcd=1; >>> scanf("%d",&n); >>> long long a[n],b[n],cnt=0,sum=0; >>> long long min=999999999; >>> scanf("%lld",&a[0]); >>> >>> for(long i=1;i<n;i++) >>> { >>> scanf("%lld",&a[i]); >>> b[i-1]=a[i]-a[0]; >>> if(min>b[i-1]) >>> min=b[i-1]; >>> } >>> >>> >>> for(int k=min;k>0;k--) >>> { >>> cnt=0; >>> for(int i=0;i<n-1;i++) >>> { >>> if(b[i]%k==0) >>> cnt++; >>> } >>> >>> if(cnt==n-1) >>> { >>> gcd=k; >>> break; >>> } >>> } >>> >>> sum=((a[n-1]-a[0])/gcd)-n+1; >>> printf("%lld\n",sum); >>> return 0; >>> >>> } >>> >>> On Sat, Mar 12, 2011 at 2:38 PM, Satyam Kapoor <satyamkapoo...@gmail.com >>> > wrote: >>> >>>> >>>> this is gud but not the best soln. >>>> >>>> -- >>>> Satyam Kapoor >>>> B.Tech 2nd year >>>> Computer Science And Engineering >>>> M.N.N.I.T ALLAHABAD >>>> >>>> -- >>>> You received this message because you are subscribed to the Google >>>> Groups "Algorithm Geeks" group. >>>> To post to this group, send email to algogeeks@googlegroups.com. >>>> To unsubscribe from this group, send email to >>>> algogeeks+unsubscr...@googlegroups.com. >>>> For more options, visit this group at >>>> http://groups.google.com/group/algogeeks?hl=en. >>>> >>> >>> >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.