How to Solve nCr%p?

Share your love

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.

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%p
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

  1. Make a 2D array of sizes n+1 and r+1
  2. 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.
  3. Check for the base case – nCn = nC0 = 1
  4. Using the Combination formula to find out the rest of the values
  5. 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

  1. Make an array of r+1 size
  2. Initialize the base case C[0] = 1
  3. 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
  4. Compute the value of nCr by adding the precious value with the current value
  5. 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.

Share your love

Leave a Reply

Your email address will not be published.