text: Binomial Coefficient | DP |  ; Function to find gcd of two numbers in O ( log ( min ( a , b ) ) ) ; Base case ; C ( n , r ) = C ( n , n - r ) better time complexity for lesser r value ; Array of elements from n - r + 1 to n ; For numbers from 1 to r find arr [ j ] such that gcd ( i , arr [ j ] ) > 1 ; If gcd > 1 , divide both by gcd ; If i becomes 1 , no need to search arr ; Single pass to multiply the numerator ; Driver code
code: using System ; class GFG { static int gcd ( int a , int b ) { if ( b == 0 ) return a ; return gcd ( b , a % b ) ; } static int nCr ( int n , int r ) { if ( r > n ) return 0 ; if ( r > n - r ) r = n - r ; int mod = 1000000007 ; int [ ] arr = new int [ r ] ; for ( int i = n - r + 1 ; i <= n ; i ++ ) { arr [ i + r - n - 1 ] = i ; } long ans = 1 ; for ( int k = 1 ; k < r + 1 ; k ++ ) { int j = 0 , i = k ; while ( j < arr . Length ) { int x = gcd ( i , arr [ j ] ) ; if ( x > 1 ) { arr [ j ] /= x ; i /= x ; } if ( i == 1 ) break ; j += 1 ; } } foreach ( int i in arr ) ans = ( ans * i ) % mod ; return ( int ) ans ; } static public void Main ( ) { int n = 5 , r = 2 ; Console . WriteLine ( " Value ▁ of ▁ C ( " + n + " , ▁ " + r + " ) ▁ is ▁ " + nCr ( n , r ) + " STRNEWLINE " ) ; } }