Compute nCr % p | Set 1 ( Introduction and Dynamic Programming Solution ) | Returns nCr % p ; Optimization for the cases when r is large ; 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 Code
< ? php function nCrModp ( $ n , $ r , $ p ) { if ( $ r > $ n - $ r ) $ r = $ n - $ r ; $ C = array ( ) ; for ( $ i = 0 ; $ i < $ r + 1 ; $ i ++ ) $ C [ $ i ] = 0 ; $ C [ 0 ] = 1 ; for ( $ i = 1 ; $ i <= $ n ; $ i ++ ) { for ( $ j = Min ( $ i , $ r ) ; $ j > 0 ; $ j -- ) $ C [ $ j ] = ( $ C [ $ j ] + $ C [ $ j - 1 ] ) % $ p ; } return $ C [ $ r ] ; } $ n = 10 ; $ r = 2 ; $ p = 13 ; echo " Value ▁ of ▁ nCr ▁ % ▁ p ▁ is ▁ " , nCrModp ( $ n , $ r , $ p ) ; ? >