LeetCode June Challenge - Day 24

Problem: LeetCode June Challenge - Day 24

Ideas

  1. Catalan numbers.
  2. Use long long to store the temporary result just in case it overflows

Solution:

class Solution {
public:
    int numTrees(int n) {
        if (n <= 1) return 1;
        // bin coef (2n n)
        long long ans = 1;
        for(int i=0; i<n; ++i)
            ans *= (2*n-i), ans /= (i+1);
        return ans/(n+1);
    }
};