Binomial Coefficients

Your task is to calculate n$n$ binomial coefficients modulo 109+7

A binomial coefficient (ab) can be calculated using the formula a!b!(a−b)!We assume that a$a$ and b$b$ are integers and 0≤b≤a

Example:

Input:  n = 3, arr = {{5, 3}, {8, 1}, {9, 5}}

Output:

10
8
126

Approach:

Java

public class BinomialCoefficient {

    public static void main(String[] args) {

        int n = 3;

        int[][] arr = { { 5, 3 }, { 8, 1 }, { 9, 5 } };

        binomialCoefficient(n, arr);

    }

    static long MOD = (long) (1e9 + 7);

    static long power(long a, long b, long m) {
        long res = 1;
        while (b > 0) {
            if (b % 2 == 1)
                res = res * a % m;
            a = a * a % m;
            b /= 2;
        }
        return res;
    }

    static long[] fact;
    static long[] invf;

    static void precompute(int n) {

        fact = new long[n + 1];
        for (int i = 0; i <= n; i++)
            fact[i] = 1;

        // find factorial of all values till
        // n
        for (int i = 1; i <= n; i++) {
            fact[i] = fact[i - 1] * i % MOD;
        }

        invf = new long[n + 1];
        for (int i = 0; i <= n; i++)
            invf[i] = 1;
        invf[n] = power(fact[n], MOD - 2, MOD);
        for (int i = n - 1; i > 0; i--)
            invf[i] = invf[i + 1] * (i + 1) % MOD;
    }

    static long nCk(int n, int k) {
        // base case
        if (k < 0 || k > n)
            return 0;
        return fact[n] * invf[k] % MOD * invf[n - k] % MOD;
    }

    static void binomialCoefficient(int n, int[][] arr) {
        precompute((int) 1e6);
        for (int i = 0; i < n; i++) {
            int a = arr[i][0];
            int b = arr[i][1];
            System.out.println(nCk(a, b));
        }
    }

}

C++

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;

long long power(long long a, long long b, long long m)
{
    long long res = 1;
    while (b)
    {
        if (b % 2)
            res = res * a % m;
        a = a * a % m;
        b /= 2;
    }
    return res;
}

vector<long long> fact, invf;

void precompute(int n)
{
    fact.assign(n + 1, 1);

    //find  factoial of all values till
    //n
    for (int i = 1; i <= n; i++)
    {
        fact[i] = fact[i - 1] * i % MOD;
    }
    invf.assign(n + 1, 1);
    invf[n] = power(fact[n], MOD - 2, MOD);
    for (int i = n - 1; i > 0; i--)
        invf[i] = invf[i + 1] * (i + 1) % MOD;
}

long long nCk(int n, int k)
{
    //base case
    if (k < 0 || k > n)
        return 0;
    return fact[n] * invf[k] % MOD * invf[n - k] % MOD;
}

void binomialCoefficient(int n, vector<vector<int>> &arr)
{
    precompute(1e6);
    for (int i = 0; i < n; i++)
    {
        int a = arr[i][0];
        int b = arr[i][1];
        cout << nCk(a, b) << "\n";
    }
}

int main()
{
    int n = 3;

    vector<vector<int>> arr = {{5, 3}, {8, 1}, {9, 5}};

    binomialCoefficient(n, arr);

    return 0;
}