Cycle and cord

Arun Nawani
Last Updated: May 13, 2022

Problem Statement

The problem states that we need to find a number of ways to draw N non-intersecting chords in a circle using 2N points. 

 

Let us try to understand the problem better with some examples. Suppose you are given N=2. That means you have 2*2 = 4 points. So there could be two ways in which you could draw N non-intersecting chords within the circle. 

 

See the figure above. We were given N=2. So we had 4 points to work within the circle, and our task was to find out the number of ways to draw N non-intersecting chords. Identifying the above 2 figures are all the possible ways to do so. 

 

The problem statement could also be viewed as the number of all possible ways of dividing the circle using N non-intersecting chords. 

Solution Approach

 

Suppose there are 8 points on a circle. If we connect any of the two points in the circle, it divides the points into two sets of points that can’t be connected because then they wouldn’t be non-intersecting chords. Let us take a look at the illustration given below for a better understanding. 

 

Here we connected points 4 and 8. This divided the points into 2 smaller sets i.e {1,2,3} and {5,6,7}. Now note that no two points from different sets can be used to draw a chord. If we do, the chord will intersect the line we just drew. 

 

This way, we devise a recurrence relation to the above problem. 

 

WAYS(N) = SUM( i = 0  to N-1) {WAYS(N) * WAYS(N-i-1)}

 

Here we iterate over i, assuming that the size of one of the sets is i and the size of another set automatically is (N-i-1) since we’ve already used a pair of points and i pair of points in one set.

 

Implementation

def NIC(N):
  n = 2 * N #number of points
 
  dp = [0]*(n + 1#dp array containing the sum
  dp[0] = 1
  dp[2] = 1
  forin range(4, n + 12):
      forin range(0, i-12):
          dp[i] += (dp[j]*dp[i-2-j])

  return dp[n]

N=int(input())
print(NIC(N))

 

 

Time and Space Complexity

Time Complexity: Since essentially the ‘dp’ array is being traversed x times, the average and the worst-case time complexity comes out to be O(N2)

 

Space Complexity: We are using auxiliary space to carry out dynamic programming. We are using a ‘dp’ array equal to the size of the number of points in the circle. Hence the space complexity is O(N)

 

FAQs

 

1). What is the recurrence relation of the above-mentioned problem?

 Ans: Here, ways(n) = sum( i=0 to n-1) {ways(n) * ways(n-i-1)}

If we assume there are i points in a set, then automatically there would N-i-1 points in other since we already used a pair of points for segregation. 

 

2). What are the time and space complexity of the algorithm implemented above?

Ans: The average time complexity, as we devised earlier, was O(N2). The auxiliary space required was of the order O(N). 

 

3). Why the dynamic programming approach? 

Ans: Using memoization greatly improves the time complexity of such problems. From a point where problems like these are almost infeasible via the brute force methods. 

 

Key Takeaways

 

‘The Circle and chord’ is one of the peculiar dynamic programming problems. Implementing and understanding this would make you better prepared to handle more interesting problems based on the concept of dynamic programming. 

 

Devising a recurrence relation is the key to tackling such problems. Problems like these are quite favourite among the recruiters. Check out our curated interview preparation courses put together by expert faculty of industry experts to crack your next product-based company interview.

 

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think