×

# Best known algos for calculating nCr % M

 22 27 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 kavishrox 285●10●17●19 accept rate: 5%

 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 kuruma 16.5k●72●143●208 accept rate: 8%
 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 ashishnegi001 152●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 surajk9035 15●1 accept rate: 0%
 0 Would someone pls xplain me what are these "inverse factorials" ?? answered 18 Nov '12, 10:10 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 jaskaran_1 525●23●35●50 accept rate: 0%
 0 What is the fastest among all the ways to calculate the value of nCr mod M? where M is definitely prime? answered 04 Apr, 06:25 imujjwalanand (suspended) accept rate: 0%
 0 Please tell explain CRT also . It would be grate help from your side :') thx answered 11 Jun, 12:00 shubham190496 1 accept rate: 0%
 toggle preview community wiki

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

Tags:

×791
×155
×111
×54