Binomial coefficient modulo prime
Given non-negative integers n and r and a prime p, return C(n, r) modulo p, where C(n, r) is the binomial coefficient "n choose r". n and r can be as large as 10^9, so you cannot precompute factorials up to n. Assume 2 <= p <= 10^9 and p is prime. If r > n the answer is 0.
Implement
ncr_mod_prime(n: int, r: int, p: int) → intExamples
in
[5,2,13]out10What a strong answer looks like
State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
0:00 of about 35 min
solution.py
InputExpectedGot
[5,2,13]10not run yetsample