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 that 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
Approach:
If we draw a chord between any two points, the current set of points gets 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 recurrence relation is similar to the recurrence relation for nth Catalan number which is equal to 2nCn / (n+1). Instead of dividing the numeration with the denomination, multiply the numerator with the modulo inverse of the denominator as division is not allowed in the modulo domain.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate x^y %mod efficientlyint 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 efficientlyint 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 chordsint 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 codeint main(){ int N = 2; // Function call cout << NoOfChords(N); return 0;} |
Java
// Java implementation of the approachclass GFG{ // Function to calculate x^y %mod efficiently static int power(long x, int y, int mod) { // Initialize the answer long res = 1; while (y != 0) { // If power is odd if ((y & 1) == 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 static int ncr(int n, int r, int mod) { // Initialize the answer 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 static int NoOfChords(int A) { // define mod value int mod = (int)(1e9 + 7); // Value of C(2n, n) 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 public static void main(String[] args) { int N = 2; // Function call System.out.println(NoOfChords(N)); }}// This code is contributed by 29AjayKumar |
Python3
# Python3 implementation of the above approach# Function to calculate x^y %mod efficientlydef power(x, y, mod): # Initialize the answer 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 (res % mod)# Function to calculate ncr%mod efficientlydef ncr(n, r, mod): # Initialize the answer res = 1 # Calculate ncr in O(r) for i in range(1,r+1): # Multiply with the numerator factor res = (res * (n - i + 1)) % mod # Calculate the inverse of factor of denominator inv = power(i, mod - 2, mod) # Multiply with inverse value res = (res * inv) % mod # Return answer value return (res%mod)# Function to return the number# of non intersecting chordsdef NoOfChords(A): # define mod value mod = 10**9 + 7 # Value of C(2n, n) ans = ncr(2 * A, A, mod) # Modulo inverse of (n+1) inv = power(A + 1, mod - 2, mod) # Multiply with modulo inverse ans = (ans * inv) % mod # Return the answer return (ans%mod)# Driver codeN = 2# Function callprint(NoOfChords(N))# This code is contributed by mohit kumar 29 |
C#
// Java implementation of the above approach using System;class GFG { // Function to calculate x^y %mod efficiently static int power(long x, int y, int mod) { // Initialize the answer long res = 1; while (y != 0) { // If power is odd if ((y & 1) == 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 static int ncr(int n, int r, int mod) { // Initialize the answer 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 static int NoOfChords(int A) { // define mod value int mod = (int)(1e9 + 7); // Value of C(2n, n) 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 public static void Main () { int N = 2; // Function call Console.WriteLine(NoOfChords(N)); }}// This code is contributed by AnkitRai01 |
Javascript
<script>// JavaScript implementation of the approach // Function to calculate x^y %mod efficiently function power(x , y , mod) { // Initialize the answer var res = 1; while (y != 0) { // If power is odd if ((y & 1) == 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 parseInt(res % mod); } // Function to calculate ncr%mod efficiently function ncr(n , r , mod) { // Initialize the answer var res = 1; // Calculate ncr in O(r) for (var i = 1; i <= r; i += 1) { // Multiply with the numerator factor res = (res * (n - i + 1)) % mod; // Calculate the inverse of // factor of denominator var inv = power(i, mod - 2, mod); // Multiply with inverse value res = (res * inv) % mod; } // Return answer value return parseInt(res % mod); } // Function to return the number // of non intersecting chords function NoOfChords( A) { // define mod value var mod = parseInt(7); // Value of C(2n, n) var ans = ncr(2 * A, A, mod); // Modulo inverse of (n+1) var inv = power(A + 1, mod - 2, mod); // Multiply with modulo inverse ans = (ans * inv) % mod; // Return the answer return parseInt(ans % mod); } // Driver code var N = 2; // Function call document.write(NoOfChords(N));// This code is contributed by 29AjayKumar </script> |
Output:
2
Time complexity : O(N*log(mod))
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
