@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
<[email protected]>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 <[email protected]
> > wrote:
>
>> sorry, @satyam: then what is the 'best' solution for this? :)
>>
>>
>> On Sat, Mar 12, 2011 at 7:06 PM, Akshata Sharma <
>> [email protected]> 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 <[email protected]
>>> > 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 [email protected].
>>>> To unsubscribe from this group, send email to
>>>> [email protected].
>>>> 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
