You are not logged in. Please login at www.codechef.com to post your questions!

×

# Best known algos for calculating nCr % M

 35 43 I have often encountered calculating nCr problems the last one being one of the IIIT-M problems but it probably had weak test cases that got easy solutions AC. The other one https://cs3.interviewstreet.com/challenges/dashboard/#problem/50877a587c389 of codesprint was completey out of my minds and hands , I tried the inverse euler , power of p in n! ( I would also like if someone could explain me the theory of this method ) but all went in vain . Anyone who could suggest probably the best algos for cases when nCr is to be calculated with large n and r with and without % M where M is prime/not prime + the above method which I coded but couldn't understand how it was so. This question is marked "community wiki". asked 15 Nov '12, 14:45 285●10●17●19 accept rate: 5%

 9 somebody plz upvote me .i need to ask some questions. answered 25 Sep '16, 09:36 62●1 accept rate: 0%
 6 I agree completely with what @kavishrox wrote... Admins, would it be possible to have some sort of "pin" feature, so that the "tutorial" like posts wouldn't go down? ;) It would greatly help newbies and ofc make this community even more respected :D Bruno answered 17 Nov '12, 04:56 3★kuruma 17.7k●72●143●209 accept rate: 8%
 2 @imujjwalanand the last method described. Keep factorials and inverse-factorials modulo p. And you can get nCr % p in O(1) time with pre-computation of O(p) and space O(p) answered 25 Sep '16, 05:44 4★kaushala 27●3 accept rate: 0%
 1 To take as example : "142857 = 27 * 11 * 13 * 37. You can find the result of nCr % m for each m = 27, 11, 13, 37." as 27 is not a prime, i hope we would have to resort to last method of finding all fact[n] and inverse-fact[n] for 27. So we want nCr and we have x! for all x, WHY do we need inverse factorial ? Is it for (n-r)! and r!. To find inverse of (n-r) and r mod M and then multiply all of their factorials and then find % M. answered 18 Nov '12, 15:08 162●1●3●7 accept rate: 0%
 1 what if do not want modulo, just ncr which does't fit in even long long? answered 15 Dec '13, 13:31 15●1 accept rate: 0%
 1 Once i had to find C(n,r) mod p for very large n,r,p but p was prime. To be exact n<=(2e9) ,r<=(1e9) and p=(2e9)+33 I really googled it but got no answer. So finally came up with an idea and it worked so i thought to share it .please correct me if it might fail in any case:- The basic idea was to divide n into parts such that we can find any factorial in O(N) time where N can be adjusted according to question's complexity, i took N to be 1e5 because i had to calculate only 3 factorial per testcase. So i divided it into 20000 (it's not random) groups each having product of all numbers in that group modulo p. 1st group contains number from 1 to 1e5 and 2nd group contains number from 1 to (2e5) and so on .generally ith group contains number from 1 to i*(1e5) let's say we are keeping these values in array f[20001]. please keep f[0] equal to 1 and keep the value of groups starting from 1 index. Please don't calculate your f array with in your program because that would be just stupid. I calculated with my IDE and kept it in a file and then copy ,pest Note:- if we increase the size of array f we can decrease the time to find factorial. How to find factorial:- let's say we have to find factorial of any random number 1567394027 steps:- n=1567394027 k=1e5 //(group size) a=n/k=15673 fac=f[a]; start=(a*k)+1 //1567300001; for(int i=start;i<=n;i++) fac=(fac*i)%p; return fac;  total number of loops=(n%k) as p is prime we can find multiplicative inverse in log(n) so i think this should work. Please comment if you find anything wrong. answered 28 Oct '17, 15:35 11●2 accept rate: 0%
 0 Would someone pls xplain me what are these "inverse factorials" ?? answered 18 Nov '12, 10:10 2★dg9_17 31●2 accept rate: 0%
 0 How would you calculate nCr mod 27? You can't use the inverse modulo here. and also one can't do this by nCr=(n-1)Cr+(n-1)C(r-1) given that the minimum space would be just 2 rows but each of size r which in this case is 1000000000? answered 17 Jul '13, 16:53 525●23●35●50 accept rate: 0%
 0 Answer is hidden as author is suspended. Click here to view. answered 04 Apr '15, 06:25 (suspended) accept rate: 0%
 0 I think we should go for Inverse Modulo in this way. This is cheap, I mean O(m). r[i] = 1 for ( i = 2 ; i < limit ; i ++ ) r[i] = ( mod - (mod/i)*r[mod%i]%mod )%mod; Here is the link Modulo_inverse link This answer is marked "community wiki". answered 18 Mar '16, 11:05 1●1 accept rate: 0%
 0 @gamabunta somebody please upvote me , i have questions to ask thank you answered 25 Sep '16, 16:38 144●2●5 accept rate: 3%
 0 In Java this works quite ok for large N,K private static BigInteger binomial(final int N, final int K) { BigInteger ret = BigInteger.ONE; for (int k = 0; k < K; k++) { ret = ret.multiply(BigInteger.valueOf(N-k)) .divide(BigInteger.valueOf(k+1)); } return ret;  } answered 21 Oct '16, 12:20 0★suja 1 accept rate: 0%
 0 Thank you for such a helpful answer, I have a conceptual doubt that why M needs to be prime for this for Modular multiplicative inverse to be applied, I mean the condition is only that A and M should be coprime for the existence of inverse so M need not be prime for that. Am I missing something , Can you please explain reason for M to be prime. answered 30 May '17, 11:55 256●7 accept rate: 8%
 -1 In c++ if you want to calculate nCr for large number of n and r, Here is the simplest logic to do that void noOfCombination(int n, int k){ int i=0; long long res=1; if (k less_than n/2) k = n - k; for(i = 0; i less_than k; i++){ res *= (n-i); res /= (i+1); } //output result return; }  enter code here answered 14 Sep '17, 15:53 -1 accept rate: 0%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,657
×228
×204
×139

question asked: 15 Nov '12, 14:45

question was seen: 71,377 times

last updated: 28 Oct '17, 15:37