[Solved]: How do I do sum of first k elements of a row of a Pascal's Triangle efficiently?

Problem Detail: 

More specifically, I want to:

$^nC_0 + ^nC_1 + ^nC_2 + ..... + ^nC_k$

I tried doing it linearly by calculating $^nC_{j+1}$ by multiplying $^nC_{j}$ with (n-j+1)/j.

The answer it gives is correct for small numbers. Since n and k can be large, I need have keep modding with P, a given prime number.

My method fails since I have to divide with j, which breaks the mod. Any suggestions?

Asked By : Rishav Banka

Answered By : D.W.

Your method is fine. You just need to know how to do modular division. Modular division is a bit different from division of two integers. You can do modular division, say $x/y \bmod p$, by computing computing the modular inverse of $y$, $y^{-1}\bmod p$, and then multiplying that by $x$. You can compute the modular inverse using the extended Euclidean algorithm.

See https://en.wikipedia.org/wiki/Modular_multiplicative_inverse.

A slight correction:

$${n \choose j+1} = {n \choose j} \times {(n-j) \over j+1}.$$

You had an off-by-one error in the formula. To do this modulo $p$, replace dvision by $j+1$ with multiplication by the modular inverse of $j+1$ modulo $p$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/59502

3.2K people like this

 Download Related Notes/Documents