Compute nCr % x

Algorithm:

• Make a dp array of ‘r+1’ size to store the result obtained by the formula explained in the approach.
• Check for the base case if r>n-r, then we need to update r = n-r
• Iterate for all the values of n starting from 1 to n and in each iteration again iterate for the values of j starting from min(i,r) to 0 and at the same time compute the value of  C(n, r) for that particular value of n using the previous values of j which depict the value of r for a particular n.
• After doing the iterations, the last element of the dp array will give the result.

Pseudo code:

// A Dynamic Programming approach to compute nCr % x
function computencr(Argument n, Argument r, Argument x)
{
 
    if (r > n - r)
        then update r = n - r;
 
    Declare dp(8) of integers
    for i = 0  to i <=r:
        Assign dp[i] = 0
    end for

    // base case
    declare dp[0] = 1; 
 
   
    for i = 1; i <= n 
        for j = minimum of (i, r) to  j > 0;
            dp[j] = (dp[j] + dp[j - 1]) % x;
        end for
    end for

    return dp[r];
}
 
Function main()
{

    declare input variables
    n = 11, r = 2, x = 6;
    print -> "Value of nCr % x is "computencr(n, r, x) 
}

Code:

// A Dynamic Programming approach to compute nCr % x
#include <bits/stdc++.h>
using namespace std;

// Compute nCr % x
int computencr(int n, int r, int x)
{

    // updation for the cases when r is large
    if (r > n - r)
        r = n - r;

    // Initializing the dp array with 0
    int dp[r + 1];
    for(int i = 0 ; i <=r ; i++)dp[i]=0;

    // Base case
    dp[0] = 1; 

    for (int i = 1; i <= n; i++) {

        // Fill entries of current row using previous row values
        for (int j = min(i, r); j > 0; j--)

            // nCj = (n-1)Cj + (n-1)C(j-1);
            dp[j] = (dp[j] + dp[j - 1]) % x;
    }
    return dp[r];
}

int main()
{
    int n = 11, r = 2, x = 6;
    cout << "Value of nCr % x is " << computencr(n, r, x) <<endl;
    return 0;
}

Output:

Value of nCr % x is 1

Time Complexity 

 O(n * r) 

The time complexity to Compute nCr % x using this approach will cost O(n * r)  time since we are running a nested loop that will calculate the value of all the nCr for values less than given n and r, which cost quadratic time complexity.

Space Complexity 

O(r)

The space complexity to Compute nCr % x using this approach will cost O(r) extra space. We are creating an extra linear array to store the results of nCr of size 'r+1', which costs linear space complexity.

Second Approach 

Another optimized approach lies in utilizing the concept of the Pascal Triangle. Instead of calculating the nCr value for every n starting from n = 0 till n = n, the approach aims at using the nth row itself for the calculation. The method proceeds by finding out a general relationship between nCr and nCr-1.So the derived formula is 

For example lets consider n = 6 and r = 4 and x = 56

C(6, 4) = C(6, 3) * (6 - 4 + 1) / 4

= 15

= 15%56 

 = 15

Lets build the pascal triangle using the given formula :

The above-given example shows that C(n, r) can be calculated by first calculating the value of C(n, r - 1) and then multiplying the result with the term (n - r + 1) / r. But this multiplication may lead to the integer overflow for large values of n. To handle this problem, we can then use modulo multiplication, and modulo division concepts in order to achieve optimizations in terms of integer overflow..

The declaration of a 1D array can be further optimized by the declaration of a single variable. However, integer overflow is still a problem that demands some other functions like finding modulo multiplication which requires a brief understanding of Euclidean Algorithm.Below is the implementation for the given approach.

Algorithm

• To compute C(n, r)%p, first check the Edge Cases, which are not possible here if (r>n) then return 0.
• If (r>n-r), which is not possible for that case, we need optimization, so for that case, we will update r = n-r.
• Make a variable, ans to calculate the final result, start iterating for all the values of r starting from 1 to r in every iteration using the derived formula generated in the above approach.
• Calculate the value of ans*(n-i+1) % x and then update the ans ans/i % x. Using this formula.
• For performing this we require the knowledge of modulo multiplication.
• Fill finding modulo multiplication for two numbers we need to find gcd using euclideian algorithm and then we also need to find multipliative inverse.
• After finding the modulo multiplication and modulo division for all the values of r and continuously updating, ans will give the final answer in the variable ans after the end of the iteration.
  
  You can also read about GCD Euclidean Algorithm here.

Pseudo code:

// dummy code to find the nCr%p based on optimal Dynamic Programming implementation 
// Returns (val1 * val2) % mod
function moduloMultiplication(Argument  val1, Argument  val2,Argument  mod)

 
    // Initialize the result
    declare ans = 0
    // Update val1 if it is greater than or equal to mod
    val1 %= mod
 
    while val2
        // If val2 is odd, add a with result
        if val2 & 1:
            update ans : ans = (ans + val1) % mod
        // Here we assume that doing 2*val1 doesn't cause overflow
        assign val1 = (2 * val1) % mod
        update : val2 = val2/2
    end 
    return ans
}
 
// C++ function for extended Euclidean Algorithm
function gcdExtended(Argument  val1, Argument  val2,Argument  xx,Argument  yy)
 
// Function to find modulo inverse of val2 if inverse does not exist it returns -1
function modInverse(Argument  val2, Argument  mod)
{
 
    // used in extended GCD algorithm
    declare xx, yy
    assign g = gcdExtended(val2, mod, &xx, &yy)
 
    // Return -1 if val2 and mod are not co-prime
    if g != 1:
        return -1
 
    // mod is added to handle negative xx
    return (xx % mod + mod) % mod
}
 
// Function for extended Euclidean Algorithm to find modular inverse.
function gcdExtended(Argument  val1, Argument  val2,Argument  xx,Argument  yy)
{
 
    // Base Case
    if val1 == 0:
        xx = 0, yy = 1
        return val2

    // To store results of recursive call
    declare x1, y1
 
    assign gcd = gcdExtended(val2 % val1, val1, &x1, &y1)
 
    // Update xx and yy using results of recursive call
    assign xx = y1 - (val2 / val1) * x1;
    assign yy = x1;
    return gcd;
}
 
// Function to compute val1/val2 under modlo mod
function modDivide(Argument val1, Argument  val2,Argument  mod)
{
 
    update val1 : val1 = val1 % mod
    assign inv = modInverse(val2, mod)
    if inv == -1
        // Divison not defined
        return 0
    else
        return (inv * val1) % mod
}
 
// Function to calculate nCr % p
function computencr(Argument  n, Argument  r, Argument  x)
{
 
    // Base case this case is not possible
    if r > n:
        then return 0
 
    // For larger r optimization need to be done
    if r > n - r:
        update r : r = n - r
 
    // ans stores the current result 
    assign ans = 1;
 
    for i = 1 to  i <= r
 
        /*
             Derived formula for calculating the result is
             C(n,r-1)*(n-r+1)/r
             this Function calculates ans*(n-i+1) % x.
        */
 
        assign ans = moduloMultiplication(ans, (n + 1 - i), x);
    
        // Function calculates ans/i % x
        assign ans = modDivide(ans, i, x);

    end for
    return ans;
}
 
function main()
{
 
    declare n = 45, r = 22, x = 1000000007
    
    // Compute nCr % x
    print:"Value of nCr % p is " << computencr(n, r, x)

}

Code:

// C++ program to find the nCr%p based on optimal Dynamic Programming implementation
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define lli long long int

// Returns (val1 * val2) % mod
ll moduloMultiplication(ll val1, ll val2,ll mod)
{

    // Initialize the result
    ll ans = 0;

    // Update val1 if it is greater than or equal to mod
    val1 %= mod;

    while (val2) {

        // If val2 is odd, add a with result
        if (val2 & 1)
            ans = (ans + val1) % mod;

        // Here we assume that doing 2*val1 doesn't cause overflow
        val1 = (2 * val1) % mod;
        val2 = val2/2;
    }
    return ans;
}

// C++ function for extended Euclidean Algorithm
lli gcdExtended(lli val1, lli val2,lli* xx,lli* yy);

// Function to find modulo inverse of val2 if inverse does not exist it returns -1
lli modInverse(lli val2, lli mod)
{

    // used in extended GCD algorithm
    lli xx, yy; 
    lli g = gcdExtended(val2, mod, &xx, &yy);

    // Return -1 if val2 and mod are not co-prime
    if (g != 1)return -1;

    // mod is added to handle negative xx
    return (xx % mod + mod) % mod;
}

// Function for extended Euclidean Algorithm to find modular inverse.
lli gcdExtended(lli val1, lli val2,lli* xx,lli* yy)
{

    // Base Case
    if (val1 == 0) {
        *xx = 0, *yy = 1;
        return val2;
    }

    // To store results of recursive call
    lli x1, y1;

    lli gcd = gcdExtended(val2 % val1, val1, &x1, &y1);

    // Update xx and yy using results of recursive call
    *xx = y1 - (val2 / val1) * x1;
    *yy = x1;
    return gcd;
}

// Function to compute val1/val2 under modlo mod
lli modDivide(lli val1, lli val2,lli mod)
{

    val1 = val1 % mod;
    lli inv = modInverse(val2, mod);
    if (inv == -1)
        // Divison not defined
        return 0;
    else
        return (inv * val1) % mod;
}

// Function to calculate nCr % p
int computencr(int n, int r, int x)
{

    // Base case this case is not possible
    if (r > n)
        return 0;

    // For larger r optimization need to be done
    if (r > n - r)
        r = n - r;

    // ans stores the current result 
    lli ans = 1;

    for (int i = 1; i <= r; i++) {

        /*
             Derived formula for calculating the result is
             C(n,r-1)*(n-r+1)/r
             this Function calculates ans*(n-i+1) % x.
        */

        ans = moduloMultiplication(ans, (n + 1 - i), x);
    
        // Function calculates ans/i % x
        ans = modDivide(ans, i, x);
    }
    return ans;
}

int main()
{

    lli n = 45, r = 22, x = 1000000007;
    
    // Compute nCr % x
    cout << "Value of nCr % p is " << computencr(n, r, x);
    return 0;
}

Output:

Value of nCr % p is 715334988

Time Complexity 

O(n) 

The time complexity to Compute nCr % x using an optimized approach will cost O(n)  time.Since we are linearly iterating for n = 0 to n = r to compute the final value of nCr % x.In each iteration, we calculate modulo multiplication using the extended euclidean algorithm, but that will cost constant time complexity.

Space Complexity 

O(1)

The space complexity to Compute nCr % x using an optimized approach will cost constant space since we have not used any extra data structure in the entire implementation to Compute nCr % x.

Note: The Pascal Triangle method for computing nCr % p works correctly only when ‘p’ is a prime number. When ‘p’ is a composite number, we need to use a different method.
One approach is to compute nCr modulo each of the prime factors of ‘p’ separately using the Pascal Triangle method and then use the Chinese Remainder Theorem to combine these results to get the final answer. 

Check out this problem - Minimum Coin Change Problem 

FAQs

1. What is the need for modulo?
   Because the highest integer data type in C/C++ is 64 bits (unsigned long long int), which can only handle data from 0 to 264 - 1, we require modulo to avoid 'integer overflow.'Modulo inverse is needed to compute the ultimate result in various difficulties, and (109 + 7) is the number that helps in this scenario because it is prime and large enough; otherwise, modular inverse tactics may fail in some cases.
    
2. What is a real-life application of modular arithmetic?
   In the field of public-key cryptography, this is commonly employed. Diffie-Hellman Key Exchange and RSA public/private keys are two algorithms that use this.
    
3. Is there any other way to solve this problem other than dynamic programming?
   Yes, we can solve this problem using basic recursion but that will cost exponential time complexity which is the worst solution. we can use memoization to optimize the recursive call.

Key Takeaways

In this article, we discussed the solution to compute nCr % x. The article focused on the different type of approaches along with the time and space complexity of both solutions.

If you want to learn more about dynamic programming and number theory concepts and want to practice some quality questions which may excel your preparation on these topics a notch higher, then you can visit our Guided Path for dynamic programming and number theory on Coding Ninjas Studio.To be more confident in data structures and algorithms, try out our DS and Algo Course. Until then, All the best for your future endeavors, and Keep Coding.