Computing nCr

iCode

Hey folks,
Today we are going to talk about how to compute nCr in the programming competitions.

1. Dynamic programming Approach :
From the high school mathematics we know a recursive method to calculate nCr i.e.
C(n,r) + C(n,r-1) = C(n+1,r)
This can also be written as
C(n,r) = C(n-1,r) + C(n-1,r-1)

It’s a very simple DP, as you can see nothing to be afraid of here.


Time complexity = O(n*r)
Space complexity = O(n*r)

2. Expand nCr

C(n,k) = n!/((n-k)!k!)
         [n(n-1)...(n-k+1)][(n-k)...(1)]
       = -------------------------------
           [(n-k)...(1)][k(k-1)...(1)]

this can also be written as

C(n,k) = 1,                 if k = 0
       = (n/k)*C(n-1, k-1), otherwise

PuedoCode

3. Using Euler’s theorem and modular multiplicative inverse

Modular Multiplicative Inverse :
In modular arithmetic, the modular multiplicative inverse of an integer ‘a’ modulo ‘m’ is an integer ‘x’ such that
ax = 1 (mod m)

Euler’s theorem :
According to Euler’s theorem, if ‘a’ is coprime…

View original post 620 more words

Advertisements
Standard

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s