PROBLEM OF THE DAY: 16/08/2023 | Nth Catalan Number
source link: https://www.geeksforgeeks.org/videos/problem-of-the-day-16082023-nth-catalan-number/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
PROBLEM OF THE DAY: 16/08/2023
Welcome to the daily solving of our PROBLEM OF THE DAY with Karan Mashru. We will discuss the entire problem step-by-step and work towards developing an optimized solution. This will not only help you brush up on your concepts of Number Theory but will also help you build up problem-solving skills.
In this video, we are given the number N. Our task is to find the Nth Catalan number.
The first few Catalan numbers for N = 0, 1, 2, 3, … are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …
Catalan Number for N is equal to the number of expressions containing N pairs of parenthesis that are correctly matched, i.e., for each of the N '(' there exist N ')' on their right and vice versa.
Since the answer can be huge we can return the answer modulo 1e9+7.
Note: Positions start from 0 as shown above.
Example :
Input:
N = 5
Output: 42
Give the problem a try before going through the video. All the best!!!
Problem Link: https://practice.geeksforgeeks.org/problems/nth-catalan-number0817/1
Solution IDE Link: https://ide.geeksforgeeks.org/online-cpp14-compiler/188528ac-ec18-48c0-8d81-ef72d9e948bd
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK