Catalan Number — Solution & Editorial

Back to the Problem

Use the recurrence C_i+1 = C_i · 2(2i+1)/(i+2); the division is exact at each step.

Complexity: O(N)