# 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.
```

## We strongly recommend that you click here and practice it, before moving on to the solution.

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
```

Working of Above formula and Pascal Triangle:
Let us see how above formula works for C(4,3)

1==========>> n = 0, C(0,0) = 1
1–1========>> n = 1, C(1,0) = 1, C(1,1) = 1
1–2–1======>> n = 2, C(2,0) = 1, C(2,1) = 2, C(2,2) = 1
1–3–3–1====>> n = 3, C(3,0) = 1, C(3,1) = 3, C(3,2) = 3, C(3,3)=1
1–4–6–4–1==>> n = 4, C(4,0) = 1, C(4,1) = 4, C(4,2) = 6, C(4,3)=4, C(4,4)=1
So here every loop on i, builds i’th row of pascal triangle, using (i-1)th row

Extension of above formula for modular arithmetic:
We can use distributive property of modulor operator to find nCr % p using above formula.

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

The above formula can implemented using Dynamic Programming using a 2D array.

The 2D array based dynamic programming solution can be further optimized by constructing one row at a time. See Space optimized version in below post for details.

Binomial Coefficient using Dynamic Programming

Below is implementation based on the space optimized version discussed in above post.

## C++

 `// A Dynamic Programming based solution to compute nCr % p ` `#include ` `using` `namespace` `std; ` ` `  `// Returns nCr % p ` `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 = 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]; ` `} ` ` `  `// Driver program ` `int` `main() ` `{ ` `    ``int` `n = 10, r = 2, p = 13; ` `    ``cout << ``"Value of nCr % p is "` `<< nCrModp(n, r, p); ` `    ``return` `0; ` `} `

## JAVA

 `// A Dynamic Programming based ` `// solution to compute nCr % p ` `import` `java.io.*; ` `import` `java.util.*; ` `import` `java.math.*; ` ` `  `class` `GFG { ` `     `  `    ``// Returns nCr % p ` `    ``static` `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[]=``new` `int``[r+``1``]; ` `        ``Arrays.fill(C,``0``); ` `     `  `        ``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 = Math.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]; ` `    ``} ` `     `  `    ``// Driver program ` `    ``public` `static` `void` `main(String args[]) ` `    ``{ ` `        ``int` `n = ``10``, r = ``2``, p = ``13``; ` `        ``System.out.println(``"Value of nCr % p is "` `                           ``+ nCrModp(n, r, p)); ` `         `  `    ``} ` `} ` ` `  ` `  `// This code is contributed by Nikita Tiwari. `

## Python3

 `# A Dynamic Programming based solution to compute nCr % p ` ` `  `# Returns nCr % p ` `def` `nCrModp(n, r, p): ` ` `  `    ``# The array C is going to store last row of ` `    ``# pascal triangle at the end. And last entry ` `    ``# of last row is nCr. ` `    ``C ``=` `[``0` `for` `i ``in` `range``(r``+``1``)] ` ` `  `    ``C[``0``] ``=` `1` `# Top row of Pascal Triangle ` ` `  `    ``# One by constructs remaining rows of Pascal ` `    ``# Triangle from top to bottom ` `    ``for` `i ``in` `range``(``1``, n``+``1``): ` ` `  `        ``# Fill entries of current row  ` `        ``# using previous row values ` `        ``for` `j ``in` `range``(``min``(i, r), ``0``, ``-``1``): ` ` `  `            ``# nCj = (n - 1)Cj + (n - 1)C(j - 1) ` `            ``C[j] ``=` `(C[j] ``+` `C[j``-``1``]) ``%` `p ` ` `  `    ``return` `C[r] ` ` `  `# Driver Program ` `n ``=` `10` `r ``=` `2` `p ``=` `13` `print``(``'Value of nCr % p is'``, nCrModp(n, r, p)) ` ` `  `# This code is contributed by Soumen Ghosh `

## C#

 `// A Dynamic Programming based ` `// solution to compute nCr % p ` `using` `System; ` ` `  `class` `GFG { ` `     `  `    ``// Returns nCr % p ` `    ``static` `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 = ``new` `int``[r + 1]; ` `         `  `        ``for``(``int` `i = 0; i < r + 1; i++) ` `            ``C[i] = 0; ` `     `  `     `  `        ``C = 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 = Math.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]; ` `    ``} ` `     `  `    ``// Driver program ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int` `n = 10, r = 2, p = 13; ` `         `  `        ``Console.Write(``"Value of nCr % p is "` `                            ``+ nCrModp(n, r, p)); ` `         `  `    ``} ` `} ` ` `  ` `  `// This code is contributed by nitin mittal. `

[

## PHP

 ` 0; ``\$j``--) ` ` `  `        ``// nCj = (n-1)Cj + (n-1)C(j-1); ` `        ``\$C``[``\$j``] = (``\$C``[``\$j``] +  ` `                  ``\$C``[``\$j` `- 1]) % ``\$p``; ` `} ` ` `  `return` `\$C``[``\$r``]; ` `} ` ` `  `// Driver Code ` `\$n` `= 10; ``\$r` `= 2;``\$p` `= 13; ` ` `  `echo` `"Value of nCr % p is "` `, ` `         ``nCrModp(``\$n``, ``\$r``, ``\$p``); ` ` `  `// This code is contributed ` `// by anuj_67. ` `?> `

Output:

`Value of nCr % p is 6`

Time complexity of above solution is O(n*r) and it requires O(n) space. There are more and better solutions to above problem.

Compute nCr % p | Set 2 (Lucas Theorem)