How to Solve nCr%p using Dynamic Programming

Problem Statement

We are given three integers n, r, and p, we have to find the value of nCr%p. Here p is a natural number greater than n and nCr is the Binomial Coefficient.

Examples

Input: n = 10, r = 2, p = 13

Output: 6

Explanation: 10C2 is 45 and 45 % 13 is 6.

Well, there are many ways of solving this problem, but in this blog, we will only discuss 3 of them as according to us they are the easier ones to understand among all.

Also, see solving nCr%p in O(n) time complexity with Fermat’s Little Theorem – but this is only valid when p is a prime number

Brute Force Approach

The brute force approach is very simple just find the nCr of the given number and take the mod of that number with p and print the result.

We will be using one of the properties of Combinations to solve nCr.

nCr = n-1Cr-1 + n-1Cr

The below code is the implementation of the brute force approach using recursion

JAVA

package com.Tekolio.Extras;

// solve nCr%p

public class solve_cobnimatrics_1 {

    public static void main(String[] args) {

        int n = 5;

        int r = 2;

        int p = 13;

       System.out.print("Value of "+n+"C"+r+" % "+p+" is "+solve(n, r, p));
    }

    public static int solve(int A, int B, int C) {

        if (B > A) // the value of r can never be greater than n

            return 0;

        if (B == 0 || B == A) // 0C0 = 1 & nCn = 1

            return 1;

        return (solve(A - 1, B - 1, C)%C + solve(A - 1, B, C)%C)%C;

    }

}

C++

#include <bits/stdc++.h>

using namespace std;

int binomialCoeff(int n, int k, int p)
{
    // Base Cases
    if (k > n)
        return 0;
    if (k == 0 || k == n)
        return 1;
 
    // Recur
    return (binomialCoeff(n - 1, k - 1, p)%p + binomialCoeff(n - 1, k, p)%p)%p;
}

int main() {
 int n = 5, k = 2, p = 13;
    cout << "Value of C(" << n << ", " << k << ") % " <<p<< " is " << binomialCoeff(n, k, p);
 return 0;
}

Python

def binomialCoeff(n, k, p):
 
    if k > n:
        return 0
    if k == 0 or k == n:
        return 1
 
    # Recursive Call
    return (binomialCoeff(n-1, k-1, p)%p + binomialCoeff(n-1, k, p)%p)%p;
 
 
# Driver Program to test ht above function
n = 5
k = 2
p = 13
print ("Value of C(%d,%d) is (%d)" % (n, k,
                                     binomialCoeff(n, k, p)))

Output

Value of 5C2 % 13 is 10

Time Complexity: O(n*max(r ,n-r))

Auxiliary Space: O(n*max(r, n-r))

But there is one problem with this code. This code is well suited to find the value of nCr only when the values of n and r are small like in our example. As soon as we try this code for a bigger value of n and r like n=50 and r=40, the result overflows and we didn’t even get a chance to take the mod of that value.

There is another problem that we can encounter with this code. This problem is not as big as the above problem but still is a problem that we should keep in mind. While doing recursion sometimes the function computes the same sub-problem again and again. See the image below

Binomial Coefficients Recursion tree for C(5,2)

As you can see from the above image, we have 3C1 two times and 2C1 three times making it the solution to overlapping subproblems.

To deal with this overlapping and also to find an efficient solution we will use dynamic programming.

Optimized Approach using Dynamic Programming

The idea is very simple, create a 2D array using dynamic programming which stores the value of nCr using the above property of Combination – nCr = (n-1)C(r-1) + (n-1)Cr, with nC0 = nCn = 1 as base case. See the below image of the DP table

Dynamic Programming table for Binomial Coefficients

nCr = (n-1)C(r-1) + (n-1)Cr

According to the formula –

nCr = (n-1)C(r-1) + (n-1)Cr

3C2 = 2C1 + 2C2

= 2 + 1 => 3 – values from the table

From the above table and the example, it is clear that we can use this dp table to make an optimized approach which can also solve our overflow problem.

Algorithm

Make a 2D array of sizes n+1 and r+1
Iterate for all the values of n (including n) starting from 0 and in each iteration again iterate till min(i, r) starting from 0.
Check for the base case – nCn = nC0 = 1
Using the Combination formula to find out the rest of the values
Returning or print the nCr value by taking its mod.

Below is the implementation of the above-discussed approach

JAVA

package com.Tekolio.Extras;

// solve nCr%p

public class solve_cobnimatrics_1 {

    public static void main(String[] args) {

        int n = 5;

        int r = 2;

        int p = 13;

        System.out.print("Value of "+n+"C"+r+" % "+p+" is "+solve(n, r, p));

    }

    public static int solve(int n, int k, int p) {

        int D[][] = new int[n + 1][k + 1];

        int i, j;

        // Calculate the value of the Binomial

        // Coefficient in bottom-up manner

        for (i = 0; i <= n; i++) {

            for (j = 0; j <= Math.min(i, k); j++) {

                // Base Cases

                if (j == 0 || j == i)

                    D[i][j] = 1;

                    // Calculate value using

                    // previously stored values

                else

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

            }

        }

        return D[n][k];

    }

}

C++

#include <bits/stdc++.h>
using namespace std;
  
int binomialCoeff(int n, int k, int p)
{
    int D[n + 1][k + 1];
    int i, j;
 
    // Calculate value of Binomial Coefficient
    // in bottom up manner
    for (i = 0; i <= n; i++) {
        for (j = 0; j <= min(i, k); j++) {
            // Base Cases
            if (j == 0 || j == i)
                D[i][j] = 1;
 
            // Calculate value using previously stored values
            else
                D[i][j] = (D[i - 1][j - 1] + D[i - 1][j])%p;
        }
    }
 
    return D[n][k];
}
  
// Driver Code
int main()
{
    int n = 41, k = 27, p = 143;
    cout << "Value of C[" << n << "][" << k << "] is "
         << binomialCoeff(n, k, p);
}

Python

def binomialCoef(n, k, p):
    C = [[0 for x in range(k+1)] for x in range(n+1)]
 
    # Calculate value of Binomial Coefficient in bottom up manner
    for i in range(n+1):
        for j in range(min(i, k)+1):
            # Base Cases
            if j == 0 or j == i:
                C[i][j] = 1
 
            # Calculate value using previously stored values
            else:
                C[i][j] = (C[i-1][j-1] + C[i-1][j])%p
 
    return C[n][k]
 
 
# Driver program to test above function
n = 5
k = 2
p=13
print("Value of C[" + str(n) + "][" + str(k) + "] is "
      + str(binomialCoef(n, k, p)))

Output

Value of 5C2 % 13 is 10

Time Complexity: O(n*r)

This is because we are running a nested loop to calculate all the values of nCr which will cost us a quadratic time complexity.

Auxiliary Space: O(n*r)

Since we are making a 2D array, this is a given.

This problem is not done yet, we can optimize it further on the time complexity part but the space complexity part.

Space Optimised Solution of the above DP Approach

The idea is very simple, in the above approach we received a space complexity of O(n*r) because we have to form a 2D array to calculate each value of nCr in one go. But what if without calculating them in one go we tackle them one at a time? Though this will not reduce the time complexity as at the end of the day we still have to calculate them all but will reduce the space complexity to O(r) – linear space complexity.

Algorithm

Make an array of r+1 size
Initialize the base case C[0] = 1
Iterate for all the values of n (including n) starting from 0 and in each iteration again iterate from min(i,r) to 0 to find all the values of r for that n
Compute the value of nCr by adding the precious value with the current value
Returning or print the nCr value by taking its mod.

JAVA

package com.Tekolio.Extras;
// solve nCr%p
public class solve_cobnimatrics_1 {
    public static void main(String[] args) {
        int n = 5;
        int r = 2;
        int p = 13;
        System.out.print("Value of "+n+"C"+r+" % "+p+" is "+solve(n, r, p));
    }
    public static int solve(int n, int k, int p) {
        int C[] = new int[k + 1];
 
        // base case
        C[0] = 1;
 
        for (int i = 1; i <= n; i++) {
            // Compute next row of pascal
            // triangle using the previous row
            for (int j = Math.min(i, k); j > 0; j--)
               C[j] = (C[j] + C[j - 1])%p;
        }
        return C[k];
    }
}

C++

// C++ program for space optimized Dynamic Programming
// Solution of Binomial Coefficient
#include <bits/stdc++.h>
using namespace std;
 
int binomialCoeff(int n, int k, int p)
{
    int C[k + 1];
    memset(C, 0, sizeof(C));
 
    C[0] = 1; // nC0 is 1
 
    for (int i = 1; i <= n; i++)
    {
       
        // Compute next row of pascal triangle using
        // the previous row
        for (int j = min(i, k); j > 0; j--)
             C[j] = (C[j] + C[j - 1])%p;
    }
    return C[k]%p;
}
 
/* Driver code*/int main()
{
    int n = 5, r = 2, p = 13;
    cout << "Value of C(" << n << "," << r << ")"<< "is " <<binomialCoeff(n, r, p);
    return 0;
}

Python

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 = 5
r = 2
p = 13
print('Value of nCr % p is', nCrModp(n, r, p))

Output

Value of 5C2 % 13 is 10

Time Complexity: O(n*r)

This is because we are running a nested loop to calculate all the values of nCr which will cost us a quadratic time complexity.

Auxiliary Space: O(r)

We are making a 1D array to store the values of nCr

In the end, we would just say that there are many ways to solve a problem, and here I have only discussed 3 such approaches which we found simpler to understand than the others.

How do I calculate nCr%p if p is not prime?

Well, there is one way that might help you – dynamic programming. Make a dp table with all values of nCr say from 0C0 to 5C5 and then use it in conjunction with the property of combinations

nCr = n-1Cr-1 + n-1Cr

Ateev Duggal

I am Ateev Duggal, a front-end web developer, and a blogger. I write blogs mainly on React JS and have an experience of over 1.5 years of freelancing. I have worked on both static and dynamic projects again using React JS like a table to show clients data which was fetched using API, a review slider, pagination component, etc, and many websites like Parent, landing pages for Ataota, and many more. Some of my blogs have been published on freecodecamp, dev.to, Medium, geeks for geeks, and many other blogging platforms and developer's communities. My Primary skills not only include React JS but HTML5, CSS3, JS, Jquery, Git, and Bootstrap also. You can visit my GitHub Profile and LinkedIn profile for more information about me or you can visit my Website at tekolio.com