i am doing the same thing without using array
long long int res = 1;
int j = 2;
for(int i = n-k+1; i <= n; i++){
res *= (long long int)i;
while(j <= k && res%j == 0){
res/=j;
j++;
}
}
On Tue, Jun 21, 2011 at 4:25 PM, kartik sachan
wrote:
>
>
@ sunny i am not getting ur apporach
but i am thinking like this..
taking an array from and intilize it to n to n-r
a[1000];
int k=0;
for(int i=n;i>=n-r;i--)
a[k++]=i;
for(int y=n-r;y>1;y--)
for(j=0;jhttp://groups.google.com/group/algogeeks?hl=en.
nCr=(n-1)Cr+(n-1)C(r-1)
--
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,
this problem is same as
*http://www.codechef.com/problems/MARBLES/*
solution to this are public
u can check for more clarification
On Tue, Jun 21, 2011 at 3:51 PM, sunny agrawal wrote:
> if it is given tha final answer fits in 64 bit signed integer then
>
> we can run a loop for i = n-r+1 to n
>
if it is given tha final answer fits in 64 bit signed integer then
we can run a loop for i = n-r+1 to n
keeping result in a 64 bit signed integer
each time multiplying with i
in this loop we need to add some code that will divide the result with r!
to do this initialize a int j to 1
and each ite
are u saying to use double in the loop to divide and multiply together?
or
to use array to divide with one by which current value of (n-r+1) is
divisible...
-
PRAMENDRA RATHI
NIT ALLAHABAD
On Tue, Jun 21, 2011 at 3:25 PM, sunny agrawal wrote:
> no w
no we can divide also with in the same loop
On Tue, Jun 21, 2011 at 3:20 PM, PRAMENDRA RATHi rathi
wrote:
> @sunny if we calculate (n-r+1)*(n-r+2).*n first and then divide this
> value by r!..
> then this method will fail with little large value of n..because first
> value will increase vry f
@sunny if we calculate (n-r+1)*(n-r+2).*n first and then divide this
value by r!..
then this method will fail with little large value of n..because first value
will increase vry fast and will go out of limit..
-
PRAMENDRA RATHI
NIT ALLAHABAD
O
DP is good when we need to use intermediate values too..
here we only need to compute nCr as a final result
so we cannot use DP here
the Logic Vandana used will be helpful here.
as nCr = n! / r! * n-r!
without loss of generality we can assume that r < n-r else we can just
replace r = n-r
then w
but for big numbers this method is very expensiveand hope
give TLE in 1 sec question where n=1000
--
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
Why cant we first cancel the higher denominator first?
Eg: For 10C3, 10!/(7!*3!) can be written as (10*9*8)/3!. This will be a
little more performing if the difference in n/2 and r is significant.
On Tue, Jun 21, 2011 at 1:09 PM, uttam tiwari wrote:
> i think it can be done by look ups..i.e. we
i think it can be done by look ups..i.e. we start wid the smallest
no..evaluate the factorial of dat n den using dis we can get the
factorial of a bigger no..
ex.
to calculate 10c3 we shud hav 3!, 7!, 10!, now firstly we evaluate 3!,
den using dis evaluate 7! as 7!=7*6*5*4*3!
n again 10!=10*9*8*7!
12 matches
Mail list logo
