text: Binomial Coefficient | DP | C ++ program to find gcd of two numbers in O ( log ( min ( a , b ) ) ) ; function to find gcd of two numbers in O ( log ( min ( a , b ) ) ) ; base case ; C ( n , r ) = C ( n , n - r ) ; 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: #include <bits/stdc++.h> NEW_LINE using namespace std ; int gcd ( int a , int b ) { if ( b == 0 ) return a ; return gcd ( b , a % b ) ; } int nCr ( int n , int r ) { if ( r > n ) return 0 ; if ( r > n - r ) r = n - r ; int mod = 1000000007 ; int arr [ r ] ; for ( int i = n - r + 1 ; i <= n ; i ++ ) { arr [ i + r - n - 1 ] = i ; } long int ans = 1 ; for ( int k = 1 ; k < r + 1 ; k ++ ) { int j = 0 , i = k ; while ( j < r ) { int x = gcd ( i , arr [ j ] ) ; if ( x > 1 ) { arr [ j ] /= x ; i /= x ; } if ( i == 1 ) break ; j += 1 ; } } for ( int i : arr ) ans = ( ans * i ) % mod ; return ( int ) ans ; } int main ( ) { int n = 5 , r = 2 ; cout << " Value ▁ of ▁ C ( " << n << " , ▁ " << r << " ) ▁ is ▁ " << nCr ( n , r ) << " STRNEWLINE " ; return 0 ; }