How to Solve nCr%p?

How to Calculate the Value of nCr%p?

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.

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;
    }
}

;

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.

Read More…