# Cancellation of factors between numerator and denominator

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