« back

nCr

Tags : dynamic-programming, geeksforgeeks, cpp, medium

Problem Statement - link #

Find nCr for given n and r.

Your Task:

Complete the function nCrModp() which takes two integers n and r as input parameters and returns the nCr mod 10^9+7.

Note: nCr does not exist when r > n. Hence, return 0 in that case.

Expected Time Complexity: O(N*R)
Expected Auxiliary Space: O(N)

Examples #

Example 1:

Input:
n = 3, r = 2
Output: 3

Example 2:

Input:
n = 4, r = 2
Output: 6

Constraints #

Solutions #

class Solution
{
    public:
    //Function to return nCr mod 10^9+7 for given n and r. 
    int nCrModp(int n, int r) 
    { 
      
      // your code here
      // pascal triangle
      if(r>n) return 0;
      if(n==r||r==0) return 1;
      if(r>(n-r)) r = n-r;
      int mod = 1e9+7;
      int dp[r+1]={0};
      dp[0]=1;
      for(int i=1;i<=n;i++){
          for(int j=min(i,r);j>0;j--)
            dp[j] = (dp[j]+dp[j-1])%mod;
      }
      return dp[r];
    } 
};