Welcome back, dear reader. So, how is it going? In this article, we will discuss a very interesting problem called
CIRCLE AND CHORDS. So, what does this problem say?
We are given a number N as the input and there are 2N points on a circle. We have to tell the number of ways in which we can draw N non-intersecting chords on this circle.
For instance, if N=3, there are 6 points on the circle. So, we can draw 3 non-intersecting chords in 5 different ways as shown below:
We recommend you refer to the CIRCLE AND CHORDS VIDEO to understand the question and clear your doubts regarding it if any. You should try to solve this problem on your own first and then refer to the solution to make your concepts strong.
Approach:
Time Complexity: O(n2) where n is the input number i.e. the number of non-intersecting chords that we have to draw. Space Complexity: O(n)
Algorithm:
If we have 2N points on a circle then the number of ways in which we can draw N non-intersecting chords in this circle is equal to the nth Catalan number. So, we have to simply generate the nth Catalan number.
Create a dp array of size n+1 where n is the input Catalan number.
Fill dp[0]=1 and dp[1]=1 and then start the outer loop from i=2 to i=n.
Start the inner loop from j=0 to less than I i.e. j=0 to j < i.
Use the formula dp[i] += dp[j] x dp[i-j-1] inside the inner loop to fill the array with the Catalan numbers.
Print dp[n] as the answer.
Explanation:
What of the Problem
The "what" of the problem is simple. We will generate the Nth Catalan Number and this will be the number of ways of having N non-intersecting chords on the circle.
Why of the Problem
Let us now try to find the "why" of the problem i.e. "why" the Nth Catalan number gives us the answer. Let us take different input values and try to analyze the number of ways in which we can draw N non-intersecting chords on the circle.
When N=0: When N=0, the number of points on the circle is 2N=0. There is still one way to draw N non-intersecting chords. Do not draw anything on the circle. This will result in 0 non-intersecting chords.
When N=1: This means that we have to draw 1 chord in a circle (a single chord will be non-intersecting only). So, N=1 means 2N=2 points are there on the circle and we can draw 1 non-intersecting chord in 1 way.
When N=2: So, when N=2, 2N=4. We have 4 points on the circle. We have 2 ways to draw 2 non-intersecting chords on the circle as shown below:
Try to find another way. You wouldn't be able to as these are the only two ways for generating non-intersecting chords. This is because the position of the points is fixed on the circle (as it should be).
Let us think about how we can conclude the number of non-intersecting chords. Let us try to draw the first chord once. If we start to draw from the 1st point, we have to draw the first chord between P1 and P2 or P1 and P3 only. Why? Think about this!!!
As you can see above, when we draw a chord between p1 and p2, there are 0 points left on the circle above the chord and 2 points left on the circle below the chords. So, if we think of this as a recursive procedure and try to draw non-intersecting chords on both the remaining places in the circle, there is 1 way to draw 0 non-intersecting chords and 1 way to draw 1 intersecting chord (i.e. for 2 points). We have multiplied these results as we have to draw 0 non-intersecting chords AND one non-intersecting chord.
The same procedure will be followed when we have drawn a chord between P1 and P3. Let us do the same procedure for N=3 also and then you would better understand it.
When N=3: When N=3, there are 2N=6 points on the circle. If we start from P1, we can draw the first chord in 3 different ways such that on either side of the chord, we have enough points in such an arrangement that we can draw non-intersecting chords on both sides.
So, we can draw the first chord between p1 and p2. We now have 0 points above this chord and 4 points below this chord. This means that we have to draw 0 non-intersecting chords above P1P2 AND 2 non-intersecting chords below P1P2. We know the number of ways of doing both. So, we get 1 x 2=2 ways i.e. there will be 2 circles with the first chord drawn between points 1 and 2 as shown below:
So, if we represent the number of ways to draw N non-intersecting chords when N=0 by C0 and the number of ways to draw N non-intersecting chords when N=2 by C2, we have till now got C0 x C2.
If we look at the second circle in img-6, we have N=1 on either side. So, this will be C1 x C1 i.e. 1 x 1=1 way.
Now, we have the third circle. The situation for the third circle is almost the same as the first circle. The answer, in this case, will be C2 x C0.
So, dear reader, what will be the total number of ways? They will be:
So, does this look familiar to you? Yes, this is the 3rd Catalan Number. So, when N=3, i.e. 6 points were there on the circle we could draw the C3 number of non-intersecting chords on the circle where C3 is the 3rd Catalan number.
If you notice, for the previous values of N too, we were getting the Nth Catalan Number as the answer.
You already know how to calculate the Nth Catalan number and that is not a very difficult task to code it as well. The main concept here is that you should get insight into how this problem got broken into the Catalan number problem.
We suggest you refer to the solution video to understand the above-explained section with even a larger example and more insight. Now that we know that we just have to generate the Nth Catalan number, let us write the code for the same.
Note: We are not discussing the Dynamic Programming array filling part as we have been solving quite a few problems on Catalan numbers now and you should know that procedure by heart till now. How of the problem
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
Scanner scn=new Scanner(System.in);
int n=scn.nextInt();
long[] dp = new long[n + 1];
dp[0] = 1; //since 0th Catalan number is 1
dp[1] = 1; //since 1st Catalan number is also 1
for(int i = 2; i < dp.length; i++){
for(int j = 0; j < i; j++){
dp[i] += dp[j] * dp[i - 1 - j];
}
}
System.out.println(dp[n]); //nth Catalan number
}
}
java;
true";
You may refer to the solution video if you have any doubts regarding this code. Let us now analyze the time and space complexity of the code above.
Time and Space Complexity Analysis
Time Complexity:
The time complexity of the above solution is O(n2) where n is the input number as the inner loop runs for n(n+1)/2 times. This makes the complexity O(n2).
Space Complexity:
The space complexity is O(n) as we make an array of size n+1.
So, dear reader, we hope that you got the time and space complexity as well. We recommend you refer to the complete solution video once to clear all your doubts if any. With this, we have completed this problem.
Suggestions:
Here are some suggestions from our side that you do not want to miss:
We suggest you watch the complete solution video once as this will give you a very deep insight into the problem and how we can break down the problem into Catalan Number Problems. This is a very interesting collection of questions that we are doing right now. This will increase your thinking skills and approach towards a problem. So, keep practicing and working hard. Till then, Happy Coding!!!
