Compute nCr % p

http://www.geeksforgeeks.org/compute-ncr-p-set-1-introduction-and-dynamic-programming-solution/

Given three numbers n, r and p, compute value of nCr mod p.

Example:

Input:  n = 10, r = 2, p = 13
Output: 6
Explanation: 10C2 is 45 and 45 % 13 is 6.

A Simple Solution is to first compute nCr, then compute nCr % p. This solution works fine when the value of nCr is small.

What if the value of nCr is large?
The value of nCr%p is generally needed for large values of n when nCr cannot fit in a variable, and causes overflow. So computing nCr and then using modular operator is not a good idea as there will be overflow even for slightly larger values of n and r. For example the methods discussed here and here cause overflow for n = 50 and r = 40.

The idea is to compute nCr using below formula

   C(n, r) = C(n-1, r-1) + C(n-1, r)
   C(n, 0) = C(n, n) = 1

   C(n, r)%p = [ C(n-1, r-1)%p + C(n-1, r)%p ] % p
   C(n, 0) = C(n, n) = 1

int nCrModp(int n, int r, int p)

{

    // The array C is going to store last row of

    // pascal triangle at the end. And last entry

    // of last row is nCr

    int C[r+1];

    memset(C, 0, sizeof(C));

 

    C[0] = 1; // Top row of Pascal Triangle

 

    // One by constructs remaining rows of Pascal

    // Triangle from top to bottom

    for (int i = 1; i <= n; i++)

    {

        // Fill entries of current row using previous

        // row values

        for (int j = min(i, r); j > 0; j--)

 

            // nCj = (n-1)Cj + (n-1)C(j-1);

            C[j] = (C[j] + C[j-1])%p;

    }

    return C[r];

}

http://www.geeksforgeeks.org/compute-ncr-p-set-2-lucas-theorem/

he time complexity of the DP based solution is O(n*r) and it required O(n) space. The time taken and extra space become very high for large values of n, especially values close to 109.

In this post, Lucas Theorem based solution is discussed. Time complexity of this solution is O(p2 * Logp n) and it requires only O(p) space.

Lucas Theorem:

Using Lucas Theorem for nCr % p:
Lucas theorem basically suggests that the value of nCr can be computed by multiplying results of niCri where niand ri are individual same-positioned digits in base p representations of n and r respectively..