×

# Best known algos for calculating nCr % M

 35 39 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%

 8 somebody plz upvote me .i need to ask some questions. answered 25 Sep '16, 09:36 51●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 2★kuruma 17.5k●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●2 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 My question refers to your explanation for - "142857 = 27 * 11 * 13 * 37. You can find the result of nCr % m for each m = 27, 11, 13, 37." since 27 is not a prime number we cannot apply lucas theorem on it. what would we do then ? answered 18 Nov '12, 14:53 162●1●3●7 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%
 toggle preview community wiki:
Preview

By Email:

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,602
×214
×170
×127

question asked: 15 Nov '12, 14:45

question was seen: 65,614 times

last updated: 28 Oct '17, 15:37