Modular Inversion technique

Software Development
#1
  1. The general formula of nCr is ( n*(n-1)(n-2) … *(n-r+1) ) / (r!). We can directly use this formula to find nCr. But that will overflow out of bound. We need to find nCr mod m so that it doesn’t overflow. We can easily do it with modular arithmetic’s formula.

for the n*(n-1)(n-2) … (n-r+1) part we can use the formula, (ab) mod m = ((a % m) * (b % m)) % m

  1. and for the 1/r! part, we need to find the modular inverse of every number from 1 to r. Then use the same formula above with a modular inverse of 1 to r. We can find modular inverse in O(r) time using the formula,

inv[1] = 1 inv[i] = − ⌊m/i⌋ * inv[m mod i] mod m To use this formula, m has to be a prime.

In the practice problem, we need to show the answer with modulo 1000000007 which is a prime.

So, this technique will work.

  • C++
  • Java
  • Python3
  • C#

// C++ program for the above approach

#include<bits/stdc++.h>

using namespace std;

// Function to find binomial

// coefficient

int binomialCoeff( int n, int r)

{

if (r > n)

return 0;

long long int m = 1000000007;

long long int inv[r + 1] = { 0 };

inv[0] = 1;

if (r+1>=2)

inv[1] = 1;

// Getting the modular inversion

// for all the numbers

// from 2 to r with respect to m

// here m = 1000000007

for ( int i = 2; i <= r; i++) {

inv[i] = m - (m / i) * inv[m % i] % m;

}

int ans = 1;

// for 1/(r!) part

for ( int i = 2; i <= r; i++) {

ans = ((ans % m) * (inv[i] % m)) % m;

}

// for (n)*(n-1)*(n-2)*...*(n-r+1) part

for ( int i = n; i >= (n - r + 1); i--) {

ans = ((ans % m) * (i % m)) % m;

}

return ans;

}

/* Driver code*/

int main()

{

int n = 5, r = 2;

cout << "Value of C(" << n << ", " << r << ") is "

<< binomialCoeff(n, r) << endl;

return 0;

}

Output

Value of C(5, 2) is 10

Time Complexity: O(n+k)

Auxiliary Space: O(k)