Count ways to divide circle using N non-intersecting chords
Given a number N, find the number of ways you can draw N chords in a circle with 2*N points such that no 2 chords intersect.
Two ways are different if there exists a chord which is present in one way and not in other.
Examples:
Input : N = 2 Output : 2 Explanation: If points are numbered 1 to 4 in clockwise direction, then different ways to draw chords are: {(1-2), (3-4)} and {(1-4), (2-3)} Input : N = 1 Output : 1 Explanation: Draw a chord between points 1 and 2.
If we draw a chord between any two points, can you observe the current set of points getting broken into two smaller sets S_1 and S_2. If we draw a chord from a point in S_1 to a point in S_2, it will surely intersect the chord we’ve just drawn.
So, we can arrive at a recurrence that Ways(n) = sum[i = 0 to n-1] { Ways(i)*Ways(n-i-1) }.
Here we iterate over i, assuming that size of one of the sets is i and 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.
C++
// cpp code to count ways // to divide circle using // N non-intersecting chords. #include <bits/stdc++.h> using namespace std; int chordCnt( int A){ // n = no of points required int n = 2 * A; // dp array containing the sum int dpArray[n + 1]={ 0 }; dpArray[0] = 1; dpArray[2] = 1; for ( int i=4;i<=n;i+=2){ for ( int j=0;j<i-1;j+=2){ dpArray[i] += (dpArray[j]*dpArray[i-2-j]); } } // returning the required number return dpArray[n]; } // Driver function int main() { int N; N = 2; cout<<chordCnt( N)<< '\n' ; N = 1; cout<<chordCnt( N)<< '\n' ; N = 4; cout<<chordCnt( N)<< '\n' ; return 0; } // This code is contributed by Gitanjali. |
Java
// Java code to count ways // to divide circle using // N non-intersecting chords. import java.io.*; class GFG { static int chordCnt( int A) { // n = no of points required int n = 2 * A; // dp array containing the sum int [] dpArray = new int [n + 1 ]; dpArray[ 0 ] = 1 ; dpArray[ 2 ] = 1 ; for ( int i = 4 ; i <= n; i += 2 ) { for ( int j = 0 ; j < i - 1 ; j += 2 ) { dpArray[i] += (dpArray[j] * dpArray[i - 2 - j]); } } // returning the required number return dpArray[n]; } public static void main(String[] args) { int N; N = 2 ; System.out.println(chordCnt(N)); N = 1 ; System.out.println(chordCnt(N)); N = 4 ; System.out.println(chordCnt(N)); } } // This code is contributed by Gitanjali. |
Python 3
# python code to count ways to divide # circle using N non-intersecting chords. def chordCnt( A): # n = no of points required n = 2 * A # dp array containing the sum dpArray = [ 0 ] * (n + 1 ) dpArray[ 0 ] = 1 dpArray[ 2 ] = 1 for i in range ( 4 , n + 1 , 2 ): for j in range ( 0 , i - 1 , 2 ): dpArray[i] + = (dpArray[j] * dpArray[i - 2 - j]) # returning the required number return int (dpArray[n]) # driver code N = 2 print (chordCnt( N)) N = 1 print (chordCnt( N)) N = 4 print (chordCnt( N)) |
C#
// C# code to count ways to divide // circle using N non-intersecting chords. using System; class GFG { static int chordCnt( int A) { // n = no of points required int n = 2 * A; // dp array containing the sum int [] dpArray = new int [n + 1]; dpArray[0] = 1; dpArray[2] = 1; for ( int i = 4; i <= n; i += 2) { for ( int j = 0; j < i - 1; j += 2) { dpArray[i] += (dpArray[j] * dpArray[i - 2 - j]); } } // returning the required number return dpArray[n]; } // Driver code public static void Main() { int N; N = 2; Console.WriteLine(chordCnt(N)); N = 1; Console.WriteLine(chordCnt(N)); N = 4; Console.WriteLine(chordCnt(N)); } } // This code is contributed by vt_m. |
PHP
<?php // PHP code to count ways // to divide circle using // N non-intersecting chords. function chordCnt( $A ) { // n = no of points required $n = 2 * $A ; // dp array containing the sum $dpArray = array_fill (0, $n + 1, 0); $dpArray [0] = 1; $dpArray [2] = 1; for ( $i = 4; $i <= $n ; $i += 2) { for ( $j = 0; $j < $i - 1; $j += 2) { $dpArray [ $i ] += ( $dpArray [ $j ] * $dpArray [ $i - 2 - $j ]); } } // returning the required number return $dpArray [ $n ]; } // Driver Code $N = 2; echo chordCnt( $N ), "\n" ; $N = 1; echo chordCnt( $N ), "\n" ; $N = 4; echo chordCnt( $N ), "\n" ; // This code is contributed by Ryuga ?> |
Javascript
<script> // JavaScript code to count ways // to divide circle using // N non-intersecting chords. function chordCnt( A){ // n = no of points required var n = 2 * A; // dp array containing the sum var dpArray = Array(n+1).fill(0); dpArray[0] = 1; dpArray[2] = 1; for ( var i=4;i<=n;i+=2){ for ( var j=0;j<i-1;j+=2){ dpArray[i] += (dpArray[j]*dpArray[i-2-j]); } } // returning the required number return dpArray[n]; } // Driver function var N; N = 2; document.write( chordCnt( N) + '<br>' ); N = 1; document.write( chordCnt( N) + '<br>' ); N = 4; document.write( chordCnt( N) + '<br>' ); </script> |
Output:
2 1 14
Time Complexity: O(n2)
Auxiliary Space: O(n)
Please suggest if someone has a better solution which is more efficient in terms of space and time.