nCr

JavaView on GFG

Problem Overview

Compute nCr (binomial coefficient) mod p.

Intuition

Compute nCr (binomial coefficient) mod p. Pascal triangle DP or Fermat little theorem with modular inverse.

Algorithm

1Pascal: dp[i][j] = dp[i-1][j-1] + dp[i-1][j] mod p.
2For large n: precompute factorials and modular inverses. nCr = n! * modinv(r!) * modinv((n-r)!) mod p.

Common Pitfalls

• Pascal for small n. Modular inverse for large n (when p is prime use Fermat: a^(p-2) mod p).

nCr.java

Java

// Approach: DP Pascal's triangle or multiplicative formula with modular inverse (for large n).
// Time: O(n*r) or O(r) Space: O(n*r) or O(r)
package solutions.nCr;

class Solution {
    public int nCr(int n, int r) {
        if (r > n)
            return 0;

        long res = 1;
        for (int i = 0; i < r; i++) {
            res = res * (n - i);
            res = res / (i + 1);
        }

        return (int) res;
    }
}

Was this solution helpful?