How to Solve nCr%p?

How to Calculate the Value of nCr%p?
How to Calculate the Value of nCr%p?

Problem Statement

Examples

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

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

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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Ateev Duggal

I am a front-end developer from India with over one year of experience in freelancing with skills like Git, HTML5, CSS3, Bootstrap 4&5, and React.