FilesExpand file tree

 master

/

binomial_coefficient.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

24 lines (15 loc) · 470 Bytes

 master

/

binomial_coefficient.py

Copy path

Top

File metadata and controls

• Code
• Blame

24 lines (15 loc) · 470 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

# A Dynamic Programming based solution to compute nCr % p

# Returns nCr % p

def nCrModp(n, r, p):

C = [0 for i in range(r+1)]

C[0] = 1 # Top row of Pascal Triangle

for i in range(1, n+1):

for j in range(min(i, r), 0, -1):

# nCj = (n - 1)Cj + (n - 1)C(j - 1)

C[j] = (C[j] + C[j-1]) % p

return C[r]

# Driver Program

n = 10

r = 2

p = 13

print('Value of nCr % p is', nCrModp(n, r, p))