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

About Khuram Ali

Programming... Programming and Programming...!!!

Posted on June 3, 2013, in Algorithms and tagged , . Bookmark the permalink. Leave a comment.

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

%d bloggers like this: