Number of Ways to Draw K Rectangles Completely Inside Each Other

Implementation

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const ll mod = 1e9 + 7;

// dp[i][j] will store the value of nCr(i,j)
ll dp[2002][2002];

// Function to construct DP
void init(){
    for(int i=0;i<=2000;i++){
        dp[i][0]=dp[i][i]=1;
        for(int j=1;j<i;j++)
            dp[i][j]=(dp[i-1][j]+dp[i-1][j-1])%mod;
    }
}

// Function to count number of ways to draw K rectangles
int main(){
    init();
    int n=3, m=4, k=1;

    // Ans = nCr(n-1, 2*k) * nCr(m-1, 2*k)
    cout<<(dp[n-1][2*k]*dp[m-1][2*k])%mod<<endl;
    return 0;
}

Output

3

Time Complexity

We have used a 2-D DP matrix to calculate nCr. It will take O(max(N, M) * max(N, M)) time to calculate the DP. Once the DP is calculated, we can find the answer in O(1). Therefore the total time complexity to count the number of ways to draw K rectangles using the above approach is O(max(N, M) * max(N, M)).

Space Complexity

The 2-D DP matrix will use O(max(N, M) * max(N, M)) space. We have not used any other data structure; therefore, the total space complexity of the approach is O(max(N, M) * max(N, M)).

Efficient Implementation

Instead of using DP to calculate the value of nCr, we can use the factorial method. This will reduce both the time and space complexity.

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const ll mod = 1e9 + 7;

// Function to return (x^y)%mod using binary exponentiation
ll  power(ll  x, ll  y){
    ll  res = 1;
    while (y > 0){
        if (y & 1)
            res = ((res%mod) *(x%mod))%mod ;
        y = y>>1;
        x = (x%mod)*(x%mod)%mod;
    }
    return res;
}
 
// Function to return N factorial % mod
ll fac(ll n){
    ll res=1;
    for (int i = 2; i <=n ; ++i) {
        res=((res%mod)  * (i%mod))%mod;
    }
    return res;
}

// Function to return nCr % mod
ll nCr(ll n ,ll r){
    if (r>n)return 0;
    return fac(n) * power(fac(r),mod-2)%mod * power(fac(n-r),mod-2) % mod;
}

// Function to count number of ways to draw K rectangles
int main(){
    int n=3, m=4, k=1;

    // Ans = nCr(n-1, 2*k) * nCr(m-1, 2*k)
    cout<<(nCr(n-1,k*2) * nCr(m-1,k*2))%mod<<endl;
    return 0;
}

Output

3

Time Complexity

Let us analyze the time taken by each function:

power(X, Y): It uses binary exponentiation to calculate X^Y. Thus it will work in O(log(Y)).

fac(N): This function iterates from 1 to N to calculate N factorial. Thus the time taken is O(N).

nCr(N, M): This function calls fac and power functions. Thus, this function's time complexity is O(N + M).

To get the final answer, we called the nCr function two times. Therefore the total time complexity to count the number of ways to draw K rectangles using the above approach is O(N + M).

Space Complexity

We have just used some variables to get our answer. Therefore, the space complexity is O(1).

FAQs

1. What are Binomial Coefficients?

Ans Binomial coefficients are the number that appears as the coefficients in the expansion of a Binomial expression. 

2. Where is Combination used?

Ans Combinations are used when we have to select a group of something without considering the order in which we select them or their arrangement.

3. What is the formula to calculate C(N, R)?

Ans Recursive: C(N, R) = C(N - 1, R) + C(N - 1, R - 1), Base Case: C(N, N)=1, C(N, 0)=1.

Factorial: C(N, R) = Factorial(N) / ( Factorial(R) * (Factorial(N - R) ).

Key Takeaways

In this article, we learned how to count the number of ways to draw K rectangles such that the following rectangle is completely inside the previous rectangle using Binomial Coefficients. We also discussed the time and space complexity of our approach. If you want to solve more such problems, you can visit Coding Ninjas Studio.

If you think that this blog helped you share it with your friends!. 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.