Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Problem Statement
2.
Solution Approach
3.
Implementation
4.
Time and Space Complexity
5.
FAQs
6.
Key Takeaways
Last Updated: Mar 27, 2024

Cycle and cord

Author Arun Nawani
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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.

 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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. 

Check out this problem - Count Ways To Reach The Nth Stair 

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.

 

Previous article
Find two Integers whose GCD is A, and the Difference Between their Squares is B
Next article
Count of Distinct Integers Belonging to First ‘N’ Terms of at least one of Given Geometric Progression Series(GPs)
Live masterclass