# Computing nCr

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

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

## Leave a comment

## Comments 0