1.
Problem
2.
Approach
3.
Implementation
3.1.
Output
4.
Time Complexity
4.1.
Space Complexity
5.
Efficient Implementation
5.1.
Output
6.
Time Complexity
6.1.
Space Complexity
7.
FAQs
8.
Key Takeaways
Last Updated: Mar 27, 2024

# Number of Ways to Draw K Rectangles Completely Inside Each Other

## Problem

Given an N * M grid, you have to draw K rectangles such that the current rectangle is completely inside the last-drawn rectangle, i.e., the new rectangle should not have any common point with the previous one. You have to count the number of ways to draw K rectangles. Since the answer can be large, you must print the answer modulo 10 ^ 9 + 7.

Note: Two ways to draw K rectangles are considered different if the final images are distinct.

Example -

Input

5 5 2

Output

1

Explanation

The only way to draw two rectangles inside a 5 * 5 grid such that the new rectangle is completely inside the previous rectangle is to draw the first rectangle of size 3 * 3 and the second rectangle of size 1 * 1 inside it. Therefore, the number of ways to draw K rectangles is 1.

Input

3 4 1

Output

3

Explanation

The figure above shows the three ways to draw one rectangle inside a 3 * 3 grid. We can show that there is no other way to draw one rectangle. Therefore the number of ways to draw K rectangles for this example is 3.

Also see, Euclid GCD Algorithm

## Approach

Let us imagine the problem in 1-dimension by considering that we have a horizontal line of length N. Drawing a rectangle can be considered equivalent to marking two points on this line such that the next two points are completely inside the previously marked points.

For example, if N is five and we have to mark two pairs of points, the following diagram shows how the final image will look.

The first pair of points will be the outermost (red), and the second will be the inner points (green). This is the only way to draw two pairs of points satisfying the condition on a line of length N.

One thing to observe here is that once we fix the points, the order gets automatically fixed. The outer pair will be marked first, the second outer pair will be marked next, and so on.

Thus our problem now reduces to finding K pairs of points inside a line of length N. That is, we have to mark 2*K points on a line of length N. This can be calculated using binomial coefficients. The final formula for 1-D will be:

nCr(N-1, 2*k)

Now, to solve the problem in 2-D, we have to consider both dimensions. Since these dimensions are independent of each other, the final answer will be the multiplication of their individual answers. Thus the number of ways to draw K rectangles in N * M grid will be:

nCr(N-1, 2*k) * nCr(M-1, 2*k)

We can compute nCr using the Dynamic programming approach.

## 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.

Live masterclass