Re: [algogeeks] finding vlaue of nCr
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!... i think d order can be minimized apprecialby...correct me if m wrong... -- 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.
Re: [algogeeks] finding vlaue of nCr
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 utmbhu...@gmail.com wrote: 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!... i think d order can be minimized apprecialby...correct me if m wrong... -- 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.
Re: [algogeeks] finding vlaue of nCr
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 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.
Re: [algogeeks] finding vlaue of nCr
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 we need to compute is (n-r+1)*(n-r+2)*.*(n) / 1.2.3.r that can be computed in O(r) On Tue, Jun 21, 2011 at 2:04 PM, kartik sachan kartik.sac...@gmail.comwrote: 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 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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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.
Re: [algogeeks] finding vlaue of nCr
@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 On Tue, Jun 21, 2011 at 2:52 PM, sunny agrawal sunny816.i...@gmail.comwrote: 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 we need to compute is (n-r+1)*(n-r+2)*.*(n) / 1.2.3.r that can be computed in O(r) On Tue, Jun 21, 2011 at 2:04 PM, kartik sachan kartik.sac...@gmail.comwrote: 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 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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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.
Re: [algogeeks] finding vlaue of nCr
no we can divide also with in the same loop On Tue, Jun 21, 2011 at 3:20 PM, PRAMENDRA RATHi rathi prathi...@gmail.comwrote: @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 On Tue, Jun 21, 2011 at 2:52 PM, sunny agrawal sunny816.i...@gmail.comwrote: 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 we need to compute is (n-r+1)*(n-r+2)*.*(n) / 1.2.3.r that can be computed in O(r) On Tue, Jun 21, 2011 at 2:04 PM, kartik sachan kartik.sac...@gmail.comwrote: 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 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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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.
Re: [algogeeks] finding vlaue of nCr
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 sunny816.i...@gmail.comwrote: no we can divide also with in the same loop On Tue, Jun 21, 2011 at 3:20 PM, PRAMENDRA RATHi rathi prathi...@gmail.com 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 fast and will go out of limit.. - PRAMENDRA RATHI NIT ALLAHABAD On Tue, Jun 21, 2011 at 2:52 PM, sunny agrawal sunny816.i...@gmail.comwrote: 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 we need to compute is (n-r+1)*(n-r+2)*.*(n) / 1.2.3.r that can be computed in O(r) On Tue, Jun 21, 2011 at 2:04 PM, kartik sachan kartik.sac...@gmail.comwrote: 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 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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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.
Re: [algogeeks] finding vlaue of nCr
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 sunny816.i...@gmail.comwrote: 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 iteration check if the ans is divisible by j keep dividing utill j divides ans or j = r+1 that will look like O(r^2) but we will be dividing with only r values so it will be O(2*r) = O(r) -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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.
Re: [algogeeks] finding vlaue of nCr
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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] finding vlaue of nCr
@ 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;y1;y--)
for(j=0;jk;j++)
if(a[j]%y==0)
{a[j]=a[j]/y;break;}
for example we take 7c3
so first array is intilize to {7,6,5,4}
then we check divisibilty by {3,2}
so 6 is divisible by 3 so put 6/3 back in array 2
so finally 7*2*5*2;
--
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.
Re: [algogeeks] finding vlaue of nCr
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 kartik.sac...@gmail.com
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;y1;y--)
for(j=0;jk;j++)
if(a[j]%y==0)
{a[j]=a[j]/y;break;}
for example we take 7c3
so first array is intilize to {7,6,5,4}
then we check divisibilty by {3,2}
so 6 is divisible by 3 so put 6/3 back in array 2
so finally 7*2*5*2;
--
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.
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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.
