Catalan numbers, 4 lines Java solution


  • 4
    J

    public int numTrees(int n) {

        double count = 1.0;
        for (double i = 1.0; i <= n; i = i + 1.0) 
            count *= ((i + n) / i);
        return (int) Math.round(count / (n+1));
    

    }


  • 0
    Y

    this is very smart! it is O(n) instead of the n^2 solution that I get with DP. BTW, what leads you to think of it as a catalan number? It is usually encountered in dividing polygons.


  • 0
    J

    Thank you! I found the recurrence relation for this counting and noticed it was the same as the one for Catalan numbers.


  • 0
    Y

    by recurrence relation, do you mean how a bigger n-sized is divided to the next smaller?


  • 0
    J

    Not just the next smaller but all the ones smaller in size. https://en.wikipedia.org/wiki/Recurrence_relation


  • 0
    T

    Since the result is int: n cannot be bigger than 19, so long instead of double would suffice:

    long count = 1;
    for (long i = 1; i <= n; i++) {
    	count = count * (i + n) / i;
    }
    return (int)(count / (n+1));

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.