Connect Chords

DP Approach

The solution to this problem can be obtained using the Catalan number formula, which gives the number of ways to arrange a given number of non-intersecting chords on a circle:

• Given 2n points on a circle, we want to draw non-intersecting chords between them.
   
• We can start by drawing a chord between any two points on the circle, which divides the circle into two regions with n-1 points each.
   
• We can then focus on drawing non-intersecting chords within these regions separately.
   
• To solve the problem of drawing non-intersecting chords within each region, we can use dynamic programming and recursively compute the number of ways to draw chords between smaller subsets of points.
   
• This approach leads to the Catalan number formula, which gives the number of ways to arrange a given number of non-intersecting chords on a circle.
   
• The formula is C(n) = (2n)! / (n! * (n+1)!), where C(n) is the number of ways to draw non-intersecting chords between n points on a circle.
   
• Therefore, the Catalan number formula provides a way to solve the problem of drawing non-intersecting chords between points on a circle systematically and efficiently.
   

Even with the pattern also, we can observe that it is the following:

• C(0) = 1
• C(1) = 1
• C(2) = 2
• C(3) = 5
• C(4) = 14
• C(5) = 42
• C(6) = 132
   

Catalan(A) = (2A)! / (A! * (A + 1)!)
 

For better understanding, check the below expression:

C(n+1) = C1 x Cn + C2 x C(n-1) ……… C(n-1) x C2 + Cn x C1
 

Example for C3

C4 = C1 x C3 + C2 x C2 + C3 x C1
 

A is the number of pairs of points on the circle, and Catalan(A) is the number of ways to draw non-intersecting chords.

Therefore, given a number A, the number of ways to draw non-intersecting chords in a circle with 2 x A points is given by the Catalan(A) formula.

Algorithm 

We can certainly find the solution if we try to solve the question with the above Catalan formula.

To understand better, follow the below table:

N is the number of points, C is the Catalan number, and W is the number of chords we can draw.

In the above table, we have seen that the Catalan series follow the solution. So we will try to implement the approach through DP. Below are the steps we need to follow:

• Define a function called FindCord that takes an integer n as input and returns a long integer.
   
• Create an array dp of size n+1 to store the number of chords for each value of n.
   
• Initialize the base cases for dp[0] and dp[1] to 1.
   
• Use dynamic programming to compute the number of chords for each value of I, where I range from 2 to n.
   
• For each value of I, set l = 0 and r = i-1.
   
• Compute the number of chords drawn between the leftmost and rightmost points on the circle using a while loop that runs while l <= i-1.
   
• Within the loop, increment dp[i] by dp[l] * dp[r] and then increment l and decrement r.
   
• Return the value of dp[n] as the number of chords that can be drawn in a circle with n points.
   
• Define a main function that calls FindCord with a value of n = 3 and prints the output to the console.

Java Implementation

import java.io.*;
import java.util.*;


public class CodingNinja {


    // Function to compute the number of chords that can be drawn in a circle with n points
    public static long FindCord(int n){
        
        // Create an array to store the number of chords for each value of n
        long [] dp= new long[n+1];
       
        // Initialize the base cases for dp[0] and dp[1]
        dp[0]=1;
        dp[1]=1;
       
        // Use dynamic programming to compute the number of chords for each value of n
        for(int i=2;i<=n;i++){
            
            // Leftmost point on the circle that can be connected by a chord
            int l=0; 
            
            // Rightmost point on the circle that can be connected by a chord
            int r=i-1; 
           
            // Compute the number of chords that can be drawn between the leftmost and rightmost points on the circle
            while(l<=i-1){
                dp[i]+=dp[l]*dp[r];
                l++;
                r--;
            }
        }
       
        // Return the number of chords that can be drawn in the circle with n points
        return dp[n];
    }
 
    // Main function to take input and call FindCord function
    public static void main(String[] args) {
       
        int n = 3;
        System.out.println(FindCord(n));
    }
}

Output

C++ implementation

#include <vector>
#include <iostream>
using namespace std;


// Function to compute the number of chords that can be drawn in a circle with n points
long long Findcord(int n){
    
    // Create a vector to store the number of chords for each value of n
    vector<long long> dp(n+1);
   
    // Initialize the base cases for dp[0] and dp[1]
    dp[0]=1;
    dp[1]=1;
   
    // Use dynamic programming to compute the number of chords for each value of n
    
    for(int i=2;i<=n;i++){
        
        // Leftmost point on the circle that can be connected by a chord
        int l=0; 
        
        // Rightmost point on the circle that can be connected by a chord
        int r=i-1; 
       
        // Compute the number of chords that can be drawn between the leftmost and rightmost points on the circle
        while(l<=i-1){
            dp[i]+=dp[l]*dp[r];
            l++;
            r--;
        }
    }
   
    // Return the number of chords that can be drawn in the circle with n points
    return dp[n];
}


// Main function to take input and call FindCord function
int main(){
    int n=3;
   
    cout << Findcord(n) << endl;
    return 0;
}

Output

Explanation

This program uses dynamic programming to compute the number of chords that can be drawn in a circle with n points. The FindChord function takes an integer n as input and returns a long integer representing the number of chords drawn in the circle.

The program initialises a vector dp of size n+1 to store the number of chords for each value of n. The vector is initialised with the base cases dp[0] = 1 and dp[1] = 1.

The program then uses dynamic programming to compute the number of chords for each value of n. It does this by iterating from i = 2 to i = n and computing the number of chords that can be drawn between the leftmost and rightmost points on the circle using a while loop.

The main function takes input from the user for n and calls the FindChord function. The program then outputs the number of chords that can be drawn in the circle with n points.

Complexity

Time Complexity

O(n^2), where n is the number of points on the circle.

Reason: In this, the function uses dynamic programming to compute the number of chords for each value of n. The function iterates from i = 2 to i = n, and for each value of i, it computes the number of chords that can be drawn between the leftmost and rightmost points on the circle using a while loop that runs from l = 0 to r = i - 1. This while loop takes O(i) time to run.

Therefore, the total time complexity of the function is:

O(1) (for initialising base cases) + O(1) (for initialising variables l and r) + O(n) (for iterating from i = 2 to i = n) + O(n^2) (for the while loop inside the for loop) = O(n^2).

Space Complexity

O(n), where n is the number of points on the circle.

Reason: In this, the function uses an array dp of size n+1 to store the number of chords for each value of i, where i ranges from 0 to n. Hence, the space required to store the array dp is n+1 units of memory.

Check out this problem - Minimum Coin Change Problem 

Frequently Asked Questions

How do we reach the DP approach to solve the Connect Chords problem?

Suppose we have 6 points on the circle. When we connect the first and fourth points, there are two points between them and outside of them. There is no need to calculate the answer for two points all the time. We can store it in the DP table.

What is the time complexity for the optimised approach of the Connect Chords problem?

The time complexity for the optimised approach is O(N * N) (where N is equal to 2 * A). We are running two nested for loops each of O(2 * A) times.

What is a chord in geometry?

A chord is a straight line segment that joins two points on a curve, such as a circle.

What is the Catalan number formula?

The Catalan number formula is a mathematical formula that gives the number of ways to form certain types of objects. For the number of chords that can be drawn between 2n points on a circle, the formula is C(n) = (2n)! / (n! * (n+1)!), where C(n) is the number of chords.

How does the optimised solution using the Catalan number formula work?

The optimised solution using the Catalan number formula computes the number of chords directly using the formula C(n) = (2n)! / (n! * (n+1)!). This formula avoids the need to compute the number of chords for each value of n using dynamic programming and is much faster, with a time complexity of O(n).

Conclusion 

We have learned about finding the number of chords that can be drawn between any two points on a circle. We started with a Java code that used dynamic programming to compute the number of chords for each value of n. We then analysed the time and space complexity of the code.

Below is the link to practice more questions:

• Chocolate Distribution Problem.
• Check If A Linked List Is Circular Linked List
   

Suppose you want to learn more about Dynamic Programming and want to practice some questions which require you to take your basic knowledge of Dynamic Programming a notch higher. In that case, you can visit our Guided Path for Dynamic Programming. To practice this problem, you can visit Practice Problem.

Until then, All the best for your future endeavours, and Keep Coding.