text: Binomial Coefficient | DP |  ; pow ( base , exp , mod ) is used to find ( base ^ exp ) % mod fast -> O ( log ( exp ) ) ; base case ; C ( n , r ) = C ( n , n - r ) Complexity for this code is lesser for lower n - r ; list to smallest prime factor of each number from 1 to n ; set smallest prime factor of each number as itself ; set smallest prime factor of all even numbers as 2 ; Check if i is prime ; All multiples of i are composite ( and divisible by i ) so add i to their prime factorization getpow ( j , i ) times ; Hash Map to store power of each prime in C ( n , r ) ; For numerator count frequency of each prime factor ; Recursive division to find prime factorization of i ; For denominator subtract the power of each prime factor ; Recursive division to find prime factorization of i ; long because mod is large and a % mod * b % mod can overflow int ; use ( a * b ) % mod = ( a % mod * b % mod ) % mod ; pow ( base , exp , mod ) is used to find ( base ^ exp ) % mod fast ; Driver code
code: import java . util . * ; class GFG { static long pow ( long b , long exp , long mod ) { long ret = 1 ; while ( exp > 0 ) { if ( ( exp & 1 ) > 0 ) ret = ( ret * b ) % mod ; b = ( b * b ) % mod ; exp >>= 1 ; } return ret ; } static int nCr ( int n , int r ) { if ( r > n ) return 0 ; if ( n - r > r ) r = n - r ; int [ ] SPF = new int [ n + 1 ] ; for ( int i = 1 ; i <= n ; i ++ ) SPF [ i ] = i ; for ( int i = 4 ; i <= n ; i += 2 ) SPF [ i ] = 2 ; for ( int i = 3 ; i * i < n + 1 ; i += 2 ) { if ( SPF [ i ] == i ) { for ( int j = i * i ; j < n + 1 ; j += i ) if ( SPF [ j ] == j ) { SPF [ j ] = i ; } } } Map < Integer , Integer > prime_pow = new HashMap < > ( ) ; for ( int i = r + 1 ; i < n + 1 ; i ++ ) { int t = i ; while ( t > 1 ) { prime_pow . put ( SPF [ t ] , prime_pow . getOrDefault ( SPF [ t ] , 0 ) + 1 ) ; t /= SPF [ t ] ; } } for ( int i = 1 ; i < n - r + 1 ; i ++ ) { int t = i ; while ( t > 1 ) { prime_pow . put ( SPF [ t ] , prime_pow . get ( SPF [ t ] ) - 1 ) ; t /= SPF [ t ] ; } } long ans = 1 , mod = 1000000007 ; for ( int i : prime_pow . keySet ( ) ) ans = ( ans * pow ( i , prime_pow . get ( i ) , mod ) ) % mod ; return ( int ) ans ; } public static void main ( String [ ] args ) { int n = 5 , r = 2 ; System . out . print ( " Value ▁ of ▁ C ( " + n + " , ▁ " + r + " ) ▁ is ▁ " + nCr ( n , r ) + "NEW_LINE"); } }