How catalan number is used to count no of non intersecting chord?
Answers
Answered by
0
Answer: pls mark me as brilliant
Step-by-step explanation:
Count ways to divide circle using N non-intersecting chord | Set-2
Given a number N. The task is to find the number of ways you can draw N chords in a circle with 2*N points such that no two chords intersect. Two ways are different if there exists a chord which is present in one way and not in other. As the answer could be large print it modulo 10^9+7.
Examples:
Input : N = 2
Output : 2
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
Recommended: Please try your approach on {IDE} first, before moving on to the solution.
Approach:
If we draw a chord between any two points, 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) }.
The above recurrance relation is similiar to the recurrance relation for nth Catalan number which is equal to 2nCn / (n+1) . Instead of dividing the numeration with the denomination, multiply the numberator with the modulo inverse of the denominator as division is not allowed in modulo domain.
Below is the implementation of the above approach:
filter_none
edit
play_arrow
brightness_4
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate x^y %mod efficiently
int power(long long x, int y, int mod)
{
// Initialize the answer
long long res = 1;
while (y) {
// If power is odd
if (y & 1)
// Update the answer
res = (res * x) % mod;
// Square the base and half the exponent
x = (x * x) % mod;
y = (y >> 1);
}
// Return the value
return (int)(res % mod);
}
// Function to calculate ncr%mod efficiently
int ncr(int n, int r, int mod)
{
// Initialize the answer
long long res = 1;
// Calculate ncr in O(r)
for (int i = 1; i <= r; i += 1) {
// Multiply with the numerator factor
res = (res * (n - i + 1)) % mod;
// Calculate the inverse of factor of denominator
int inv = power(i, mod - 2, mod);
// Multiply with inverse value
res = (res * inv) % mod;
}
// Return answer value
return (int)(res%mod);
}
// Function to return the number
// of non intersecting chords
int NoOfChords(int A)
{
// define mod value
int mod = 1e9 + 7;
// Value of C(2n, n)
long long ans = ncr(2 * A, A, mod);
// Modulo inverse of (n+1)
int inv = power(A + 1, mod - 2, mod);
// Multiply with modulo inverse
ans = (ans * inv) % mod;
// Return the answer
return (int)(ans%mod);
}
// Driver code
int main()
{
int N = 2;
// Function call
cout << NoOfChords(N);
return 0;
}
Output:
2
Time complexity : O(N*log(mod))
Recommended Posts:
Length of the chord of the circle whose radius and the angle subtended at the center by the chord is given
Angle subtended by the chord to center of the circle when the angle subtended by the another equal chord of a congruent circle is given
Length of the chord the circle if length of the another chord which is equally inclined through the diameter is given
Divide two integers without using multiplication, division and mod operator | Set2
Count number of ways to divide an array into two halves with same sum
Shortest distance from the centre of a circle to a chord
Find the Diameter or Longest chord of a Circle
Count number of ways to divide a number in 4 parts
Minimum cuts required to divide the Circle into equal parts
Program to calculate angle on circumference subtended by the chord when the central angle subtended by the chord is given
Find the number of ways to divide number into four parts such that a = c and b = d
Ways to divide a binary array into sub-arrays such that each sub-array contains exactly one 1
Count digits in given number N which divide N
Distance of chord from center when distance between center and another equal length chord is given
Count pieces of circle after N cuts
Similar questions