UVa - 10223 Solution ( How Many Nodes Solution )[ C & C++ Code ]

=>Try Yourself First. For help Scroll Down .

Clearance : Normally you have the number of Nodes and You had to Find out how many trees you will Form through those Nodes . But Here problem is Reverse . You have the Number of Trees . You have to Find the Number of Nodes . To find the number of Trees from N nodes you have to use The Rules for Catalan Numbers . That is :

     Its a Derived DP formula . The Main Formula is Given Below :

As the Maximum Length of input may be 25 . Precalculate all the Catalan Numbers  from 1 to 25 . Then find whether the input is Match with i'th Catalan Numbers  . If it is the Print ' i ' .

Code :

#include<bits/stdc++.h>

using namespace std;

long long int catalan[30];

int solve()
{
    catalan[0]=1;
    int i = 0;
    while(i<25)
    {
        catalan[i+1] = (catalan[i] * (4*i + 2))/(i + 2);
        i++;
    }
}

int main()
{
    solve();
    long long int n;
    while(scanf("%lld",&n)==1)
    {
        for(int i = 1; i<25; i++)
        {
            if(n==catalan[i])
                 { printf("%d\n",i); break; }
        }
    }
    return 0;
}
/*
I have solved this by Catalan Expression's Recurrence Relation
C(n) = (2*(2n+1)/(n+2)) * C(n-1);
Where C0 = 1
*/

=>Question or Need Help ?? Leave a Comment .