Cancellation of factors between numerator and denominator

Software Development
#1

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))