nCr Mod Prime

119k
0

Given three integers n, r, and a prime number p, find the value of: nCr % p Here, nCr means the number of ways to choose r items from n items.

In simple words, the task is to compute combinations, but return the answer after dividing it by p and keeping only the remainder.

Example 1

Input: n = 10, r = 2, p = 13

Output: 6

Explanation: 10C2 = 45, and 45 % 13 = 6.

Example 2

Input: n = 1000, r = 900, p = 13

Output: 8

Explanation: Here n is much larger than p, so a direct factorial-based modular inverse method is not reliable. Lucas Theorem handles this case correctly, and the final remainder is 8.

Optimal Approach using Fermat Theoram

The combination formula is: nCr = n! / (r! * (n-r)!) The problem is that division under modulo is not done like normal arithmetic. A direct divide is not valid. This is where the prime modulus becomes useful. When p is prime and a number x is not divisible by p, Fermat's Little Theorem says:

x(p-1) % p = 1 From that, the modular inverse of x becomes:

x-1% p = x(p-2) % p So instead of dividing by r! * (n-r)!, the work changes into multiplying by its modular inverse.

This is the standard fast approach when p is prime and n < p. That condition matters because if n >= p, then n! % p becomes 0, and the direct factorial-inverse formula can break even when the final answer is not 0.

Algorithm

  • First, check whether r is outside the valid range. If r > n, return 0 because the selection is impossible.

  • If r is 0 or equal to n, return 1 because there is only one valid way in both cases.

  • Replace r with min(r, n - r) so fewer factorial terms need to be handled.

  • If n >= p, do not use this direct method. That restriction is important because factorial values up to n will include p, which makes normal modular inverse division invalid here.

  • Compute n! % p, r! % p, and (n-r)! % p using loops.

  • Multiply r! and (n-r)!, then take modulo p. This gives the denominator under modulo.

  • Find the modular inverse of that denominator using fast exponentiation with power p - 2. This step works because p is prime.

  • Multiply n! by the modular inverse of the denominator and take modulo p. That final multiplication gives nCr % p.

Dry Run

Computer ncR mod Prime Optimal Dry Run

Computer ncR mod Prime Optimal Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
/*Computes base raised to exponent
under modulo using binary power.*/
long long powerMod(long long base, long long exponent, int mod) {
// Stores the running answer under modulo.
long long result = 1;
// Keep base inside modulo before the loop starts.
base %= mod;
while (exponent > 0) {
// Multiply now when the current bit contributes.
if (exponent & 1LL) {
result = (result * base) % mod;
}
// Square the base for the next binary bit.
base = (base * base) % mod;
// Shift right because the current bit is already handled.
exponent >>= 1;
}
return result;
}
/*Computes modular inverse when mod
is prime and value is not divisible by mod.*/
long long modInverse(long long value, int mod) {
return powerMod(value, mod - 2, mod);
}
public:
/*Computes nCr modulo p using factorials
and Fermat's Little Theorem.*/
int nCrModPrimeFermat(int n, int r, int p) {
// Return 0 because choosing more than n items is impossible.
if (r > n) {
return 0; // Fixed: Changed 0n to 0
}
// Return 1 because nC0 and nCn always equal 1.
if (r == 0 || r == n) {
return 1;
}
// Use the smaller side because nCr equals nC(n-r).
r = min(r, n - r);
// Stop here because this direct method needs n to stay below p.
if (n >= p) {
return -1; // Fixed: Changed -1n to -1
}
// Stores n! under modulo p.
long long numerator = 1;
for (int i = 2; i <= n; i++) {
// Multiply each number into n! under modulo p.
numerator = (numerator * i) % p;
}
// Stores r! under modulo p.
long long factR = 1;
for (int i = 2; i <= r; i++) {
// Multiply each number into r! under modulo p.
factR = (factR * i) % p;
}
// Stores (n-r)! under modulo p.
long long factNR = 1;
for (int i = 2; i <= n - r; i++) {
// Multiply each number into (n-r)! under modulo p.
factNR = (factNR * i) % p;
}
// Combine the denominator terms before taking inverse.
long long denominator = (factR * factNR) % p;
// Multiply by modular inverse instead of normal division.
return (int)((numerator * modInverse(denominator, p)) % p);
}
};
// Driver code starts
int main() {
int n = 10;
int r = 2;
int p = 13;
Solution obj;
cout << obj.nCrModPrimeFermat(n, r, p) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(n + log p), because factorial values are built in O(n) time and modular exponentiation takes O(log p) time.

Space Complexity: O(1), because constant extra space is used in this direct implementation.

Optimal Approach using Lucas Theoram

The Fermat-based factorial formula is fast, but it has a very important limitation: the direct version needs n < p. So what happens when n is much larger than p, but the modulus is still prime?

Lucas Theorem solves exactly that case. It breaks n and r into digits in base p and turns one large combination problem into several much smaller combination problems:

nCr % p = product of (niCri) % p

Here ni and ri are the digits of n and r in base p.

This idea matters because every smaller piece now has values less than p, so the tricky large factorial issue disappears. Instead of fighting one huge combination, the work is divided into safe little subproblems.

This is one of the most important advanced approaches for nCr % p, and it should definitely be known when the problem allows very large values.

Algorithm

  • First, check whether r is outside the valid range. If r > n, return 0 because the combination does not exist.

  • If r is 0, return 1 because there is exactly one way to choose nothing.

  • Take the last base-p digit of n by n % p, and take the last base-p digit of r by r % p.

  • If the digit of r is greater than the digit of n, return 0 immediately. This matters because that small combination is impossible, so the full answer also becomes impossible.

  • Compute the small combination niCri % p for the current digits. A simple DP method is enough here because both digits are smaller than p.

  • Remove the last digits by dividing both n and r by p, then solve the remaining higher-digit problem.

  • Multiply the current small answer with the recursive answer of the remaining digits, and take modulo p.

  • When r becomes 0, stop and return 1 because no more digit choices are left.

Dry Run

Computer ncR mod Prime Optimal Dry Run

Computer ncR mod Prime Optimal Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
/*
Computes small nCr modulo p when
both n and r are less than p.
*/
int smallNCrModP(int n, int r, int p) {
// Return 0 because choosing more than n items is impossible.
if (r > n) {
return 0;
}
// Return 1 because nC0 and nCn always equal 1.
if (r == 0 || r == n) {
return 1;
}
// Use the smaller side because nCr equals nC(n-r).
r = min(r, n - r);
// Stores one Pascal row for the current small problem.
vector<int> dp(r + 1, 0);
// There is always one way to choose 0 items.
dp[0] = 1;
for (int i = 1; i <= n; i++) {
// Stay inside the valid part of the current Pascal row.
int limit = min(i, r);
for (int j = limit; j >= 1; j--) {
// Add the two parent values from Pascal's Identity.
dp[j] = (dp[j] + dp[j - 1]) % p;
}
}
return dp[r];
}
public:
/*
Computes nCr modulo prime p even
when n can be much larger than p.
*/
int nCrModPrimeLucas(long long n, long long r, int p) {
// Return 0 because choosing more than n items is impossible.
if (r > n) {
return 0;
}
// Return 1 because no more choices are left to make.
if (r == 0) {
return 1;
}
// Take the current base-p digit from n.
int ni = (int)(n % p);
// Take the current base-p digit from r.
int ri = (int)(r % p);
// Return 0 because this digit-level combination is impossible.
if (ri > ni) {
return 0;
}
// Solve the current digit-level combination first.
int current = smallNCrModP(ni, ri, p);
// Solve the remaining higher digits recursively.
int remaining = nCrModPrimeLucas(n / p, r / p, p);
// Multiply both parts because Lucas combines digit answers.
return (int)((1LL * current * remaining) % p);
}
};
// Driver code starts
int main() {
long long n = 1000;
long long r = 900;
int p = 13;
Solution obj;
cout << obj.nCrModPrimeLucas(n, r, p) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(p2 * logp n) in this implementation, because each base-p digit uses a small DP combination computation.

Space Complexity: O(p + logp n), because the helper DP array uses O(p) space and the recursion depth is O(logp n).

Interview follow-up Questions

Because modulo arithmetic does not allow normal division in the usual sense. Division must be replaced by multiplication with a modular inverse, and that inverse exists only in valid conditions.

Maths

Read Similar Blogs

Two PointerSortingBinary SearchArraysMaths

Koko Eating Bananas: Find the Minimum Eating Speed

There are N piles of bananas, the i th pile has piles[i] bananas. The guards have gone and will come back in h hours. Koko can decide her bananas-per-hour eating speed of k . Each hour, she chooses...

109k
Two PointerSortingMathsHeapBinary SearchArrays

Minimize Maximum Distance Between Gas Stations

You are given a sorted array representing the exact integer positions of several gas stations on a highway. You are also given an integer k, which represents the number of brand new gas stations yo...

120.4k
Two PointerSortingMathsBinary SearchArrays

Book Allocation Problem: Allocate Minimum Pages

Given an array pages , where pages[i] represents the number of pages in the i-th book, and an integer students , allocate all books among the students. The allocation must follow these rules: Each...

63.2k
Comments0