Compute nCr % p | Set 1 ( Introduction and Dynamic Programming Solution ) | Returns nCr % p ; Optimization for the cases when r is large compared to n - r ; The array C is going to store last row of pascal triangle at the end . And last entry of last row is nCr . ; Top row of Pascal Triangle ; One by constructs remaining rows of Pascal Triangle from top to bottom ; Fill entries of current row using previous row values ; nCj = ( n - 1 ) Cj + ( n - 1 ) C ( j - 1 ) ; Driver Program
def nCrModp ( n , r , p ) : NEW_LINE INDENT if ( r > n - r ) : NEW_LINE INDENT r = n - r NEW_LINE DEDENT C = [ 0 for i in range ( r + 1 ) ] NEW_LINE C [ 0 ] = 1 NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT for j in range ( min ( i , r ) , 0 , - 1 ) : NEW_LINE INDENT C [ j ] = ( C [ j ] + C [ j - 1 ] ) % p NEW_LINE DEDENT DEDENT return C [ r ] NEW_LINE DEDENT n = 10 NEW_LINE r = 2 NEW_LINE p = 13 NEW_LINE print ( ' Value ▁ of ▁ nCr ▁ % ▁ p ▁ is ' , nCrModp ( n , r , p ) ) NEW_LINE