Compute nCr % p

Problem Statement

The problem “Compute nCr % p” states that you are required to find binomial coefficient modulo p. So you first must know about the binomial coefficient. We have already discussed that in a previous post. You can check that here.

Example

n = 5, r = 2, p = 6

4

Explanation

nCr = 5C2 = 10
nCr % p = 10%6 = 4
So, we calculated 5C2 using the formula of the binomial coefficient. Then took the modulo over the value.

Approach

In the previous post regarding the calculation of the binomial coefficient. What we did was first computed the values which were required to solve nCr. We used dynamic programming to solve the problem but then we were only calculating the value of nCr. Not the binomial coefficient modulo some number p. The naive approach would be to first calculate the binomial coefficient and then take the modulo p. But there is a limitation on this calculation. You can’t calculate Binomial coefficients for large numbers as that will result in an overflow. So we need to find a way that can produce a correct result without going into integer overflow.

One thing that we can do is keep on taking modulus while the calculation of our binomial coefficient. So the only change form the solution of previous post is that we will take modulus during the calculations. Thus our recursive formula will change a bit, but the transitions remain the same. And the current binomial coefficient is dependent on the same states as it was previously.

Code

C++ code to compute nCr % p

#include<bits/stdc++.h>
using namespace std;
// this function just makes our pascal triangle
int computeBinomialCoefficientsModuloP(int n, int r, int p)
{
  int C[r+1];
    C[0] = 1;
    for (int i = 0; i <= n; i++)
    {
        // since the recursive formula is dependent on current and previous binomial coefficient on i
        // if we had run a forward loop our algorithm would have not given us a correct result
        for (int j = min(i, r); j >0 ; j--)
        {
            C[j] = (C[j - 1] + C[j])%p; // use recursive formula
        }
    }
    return C[r];
}

int main()
{
    int n,k,p;cin>>n>>k>>p;
    // here n & k do not satisfy the properties of binomial coefficient
    // then we will answer it as 0
    int val = computeBinomialCoefficientsModuloP(n, k, p);
    if(val != 0)
      cout<<val<<endl;
    else
      cout<<0<<endl;
}

5 2 4

2

Java code to compute nCr % p

import java.util.*;
class Main{
  // this function just makes our pascal triangle
  static int computeBinomialCoefficientsModuloP(int n, int r, int p) 
  {
  	int C[] = new int[r+1];
  	C[0] = 1;
    for (int i = 0; i <= n; i++) 
    { 
      // since the recursive formula is dependent on current and previous binomial coefficient on i
      // if we had run a forward loop our algorithm would have not given us a correct result 
      for (int j = Math.min(i, r); j >0 ; j--) 
      {
          C[j] = (C[j - 1] + C[j])%p; // use recursive formula
      }
    } 
    return C[r]; 
  }
  
  public static void main(String[] args)
  {
      Scanner sc = new Scanner(System.in);
      // here n & k do not satisfy the propertoes of binomial coefficient
      // then we will answer it as 0
      int n = sc.nextInt();
      int k = sc.nextInt();
      int p = sc.nextInt();
      int val = computeBinomialCoefficientsModuloP(n, k, p);
      if(val != 0)
        System.out.println(val);    
      else
        System.out.println(0);
   }
}

5 2 4

2

Complexity Analysis

Time Complexity

O(N*R), where N and R are the inputs given. This is because when we were calculating our Binomial Coefficient, we had an outer loop and one inner loop.

Space Complexity

O(R), since we made an array to store the intermediate values, and thus the space complexity is linear.