Program to calculate the value of nCr Efficiently
Given two numbers n, r ( n>=r ). The task is to find the value of C(n, r) for big value of n.
Examples:
Input: n = 30, r = 15 Output: 155117520 C(30, 15) is 155117520 by 30!/((30-15)!*15!) Input: n = 50, r = 25 Output: 126410606437752
Approach: A simple code can be created with the following knowledge that :
C(n, r) = [n * (n-1) * .... * (n-r+1)] / [r * (r-1) * .... * 1]
However, for big values of n, r the products may overflow, hence during each iteration we divide the current variables holding value of products by their gcd.
Below is the required implementation:
C++
// C++ implementation to find nCr #include <bits/stdc++.h> using namespace std; // Function to find the nCr void printNcR( int n, int r) { // p holds the value of n*(n-1)*(n-2)..., // k holds the value of r*(r-1)... long long p = 1, k = 1; // C(n, r) == C(n, n-r), // choosing the smaller value if (n - r < r) r = n - r; if (r != 0) { while (r) { p *= n; k *= r; // gcd of p, k long long m = __gcd(p, k); // dividing by gcd, to simplify // product division by their gcd // saves from the overflow p /= m; k /= m; n--; r--; } // k should be simplified to 1 // as C(n, r) is a natural number // (denominator should be 1 ) . } else p = 1; // if our approach is correct p = ans and k =1 cout << p << endl; } // Driver code int main() { int n = 50, r = 25; printNcR(n, r); return 0; } |
Java
// Java implementation to find nCr class GFG { // Function to find the nCr static void printNcR( int n, int r) { // p holds the value of n*(n-1)*(n-2)..., // k holds the value of r*(r-1)... long p = 1 , k = 1 ; // C(n, r) == C(n, n-r), // choosing the smaller value if (n - r < r) { r = n - r; } if (r != 0 ) { while (r > 0 ) { p *= n; k *= r; // gcd of p, k long m = __gcd(p, k); // dividing by gcd, to simplify // product division by their gcd // saves from the overflow p /= m; k /= m; n--; r--; } // k should be simplified to 1 // as C(n, r) is a natural number // (denominator should be 1 ) . } else { p = 1 ; } // if our approach is correct p = ans and k =1 System.out.println(p); } static long __gcd( long n1, long n2) { long gcd = 1 ; for ( int i = 1 ; i <= n1 && i <= n2; ++i) { // Checks if i is factor of both integers if (n1 % i == 0 && n2 % i == 0 ) { gcd = i; } } return gcd; } // Driver code public static void main(String[] args) { int n = 50 , r = 25 ; printNcR(n, r); } } |
Python3
# Python3 implementation to find nCr from math import * # Function to find the nCr def printNcR(n, r): # p holds the value of n*(n-1)*(n-2)..., # k holds the value of r*(r-1)... p = 1 k = 1 # C(n, r) == C(n, n-r), # choosing the smaller value if (n - r < r): r = n - r if (r ! = 0 ): while (r): p * = n k * = r # gcd of p, k m = gcd(p, k) # dividing by gcd, to simplify product # division by their gcd saves from # the overflow p / / = m k / / = m n - = 1 r - = 1 # k should be simplified to 1 # as C(n, r) is a natural number # (denominator should be 1 ) else : p = 1 # if our approach is correct p = ans and k =1 print (p) # Driver code if __name__ = = "__main__" : n = 50 r = 25 printNcR(n, r) # this code is contributed by # ChitraNayal |
C#
// C# implementation to find nCr using System; public class GFG { // Function to find the nCr static void printNcR( int n, int r) { // p holds the value of n*(n-1)*(n-2)..., // k holds the value of r*(r-1)... long p = 1, k = 1; // C(n, r) == C(n, n-r), // choosing the smaller value if (n - r < r) { r = n - r; } if (r != 0) { while (r > 0) { p *= n; k *= r; // gcd of p, k long m = __gcd(p, k); // dividing by gcd, to simplify // product division by their gcd // saves from the overflow p /= m; k /= m; n--; r--; } // k should be simplified to 1 // as C(n, r) is a natural number // (denominator should be 1 ) . } else { p = 1; } // if our approach is correct p = ans and k =1 Console.WriteLine(p); } static long __gcd( long n1, long n2) { long gcd = 1; for ( int i = 1; i <= n1 && i <= n2; ++i) { // Checks if i is factor of both integers if (n1 % i == 0 && n2 % i == 0) { gcd = i; } } return gcd; } // Driver code static public void Main() { int n = 50, r = 25; printNcR(n, r); } // This code is contributed by ajit. } |
PHP
<?php // PHP implementation to find nCr // Function to find the nCr function printNcR( $n , $r ) { // p holds the value of n*(n-1)*(n-2)..., // k holds the value of r*(r-1)... $p = 1; $k = 1; // C(n, r) == C(n, n-r), // choosing the smaller value if ( $n - $r < $r ) { $r = $n - $r ; } if ( $r != 0) { while ( $r > 0) { $p *= $n ; $k *= $r ; // gcd of p, k $m = __gcd( $p , $k ); // dividing by gcd, to simplify product // division by their gcd saves from the overflow $p /= $m ; $k /= $m ; $n --; $r --; } // k should be simplified to 1 // as C(n, r) is a natural number // (denominator should be 1 ) . } else { $p = 1; } // if our approach is correct p = ans and k =1 echo ( $p ); } function __gcd( $n1 , $n2 ) { $gcd = 1; for ( $i = 1; $i <= $n1 && $i <= $n2 ; ++ $i ) { // Checks if i is factor of both integers if ( $n1 % $i == 0 && $n2 % $i == 0) { $gcd = $i ; } } return $gcd ; } // Driver code $n = 50; $r = 25; printNcR( $n , $r ); //This code is contributed by Sachin. ?> |
Javascript
<script> // Javascript implementation to find nCr function __gcd(n1, n2) { var gcd = 1; for ( var i = 1; i <= n1 && i <= n2; ++i) { // Checks if i is factor of both integers if (n1 % i == 0 && n2 % i == 0) { gcd = i; } } return gcd; } // Function to find the nCr function printNcR(n, r) { // p holds the value of n*(n-1)*(n-2)..., // k holds the value of r*(r-1)... var p = 1, k = 1; // C(n, r) == C(n, n-r), // choosing the smaller value if (n - r < r) r = n - r; if (r != 0) { while (r) { p *= n; k *= r; // gcd of p, k var m = __gcd(p, k); // dividing by gcd, to simplify // product division by their gcd // saves from the overflow p /= m; k /= m; n--; r--; } // k should be simplified to 1 // as C(n, r) is a natural number // (denominator should be 1 ) . } else p = 1; // if our approach is correct p = ans and k =1 document.write(p); } // Driver code var n = 50, r = 25; printNcR(n, r); </script> |
Output
126410606437752
Time Complexity: O( R Log N)
Auxiliary Space: O(1), since no extra space has been taken.