The answer fits in 64 bit range.
The calculations done are of the form D = (A*B) / C. Here {A,B,C,D}
can be represented are 64 bit integers.
But we cannot say that A*B will be a 64 bit integer and will cause
overflows.
To avoid this,
Let's say G=GCD(A,C). Then the above can be written as D = ((A/G) *
B)/ (C/G).
Now, C/G will divide B.
So, our calculation becomes, D= A/G; D= D * (B/(C/G));
You can that maximum value here is from the set {A/G , B/(C/G) , D}.
All of which are 64-bit integers.
C function :
typedef unsigned long long ULL
ULL bin(ULL n,ULL k)
{
if(n<k) return 0;
if(k>n-k) k=n-k;
ULL ans=1;
for(ULL i=1;i<=k;i++)
{
ULL d=gcd(p,i);
ans/=d;
ans*=(n-i+1)/(i/d);
}
return ans;
}
On Jun 21, 10:57 pm, kartik sachan <kartik.sac...@gmail.com> wrote:
> hey anika here n<=1 and n>=0 so its 1 only
--
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.
