nCr = (n-r+1)(n-r+2)….*n / (r!)
Create an array arr of numbers from n-r+1 to n which will be of size r. As nCr is always an integer, all numbers in the denominator should cancel with the product of numerator (represented by arr).
for i = 1 to i = r,
search arr, if arr[j] and i have gcd>1, divide both by the gcd and when i becomes 1, stop the search
Now, the answer is just the product of arr, whose value mod 10^9+7 can be found using a singe pass and the formula use (a*b)%mod = (a%mod * b%mod)%mod
- Java
- Python3
import java.util.*;
class GFG
{
static int gcd( int a, int b) // function to find gcd of two numbers in O(log(min(a,b)))
{
if (b== 0 ) return a;
return gcd(b,a%b);
}
static int nCr( int n, int r)
{
if (r>n) // base case
return 0 ;
if (r>n-r) // C(n,r) = C(n,n-r) better time complexity for lesser r value
r = n-r;
int mod = 1000000007 ;
int [] arr = new int [r]; // array of elements from n-r+1 to n
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++) // for numbers from 1 to r find arr[j] such that gcd(i,arr[j])>1
{
int j= 0 , i=k;
while (j<arr.length)
{
int x = gcd(i,arr[j]);
if (x> 1 )
{
arr[j] /= x; // if gcd>1, divide both by gcd
i /= x;
}
if (i== 1 )
break ; // if i becomes 1, no need to search arr
j += 1 ;
}
}
for ( int i : arr) // single pass to multiply the numerator
ans = (ans*i)%mod;
return ( int )ans;
}
// Driver code
public static void main(String[] args)
{
int n = 5 , r = 2 ;
System.out.print( "Value of C(" + n+ ", " + r+ ") is "
+nCr(n, r) + "\n" );
}
}
// This code is contributed by Gautam Wadhwani
Output
Value of C(5, 2) is 10
Time Complexity: O(( min(r, n-r)^2 ) * log(n)), useful when n >> r or n >> (n-r)
Auxiliary Space: O(min(r, n-r))