Catalan Numbers

/*
 * Problem : Print the first n terms of the catalan numbers.
 * Input   : One integer n (number of terms).
 * Output  : The first n terms on one line, separated by a space.
 * Approach: Calculate each term from the earlier terms.
 * Time    : O(n)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        int count = new Scanner(System.in).nextInt();

        // Step 1: Make an array for the terms. Index 0 holds the first term.
        long[] terms = new long[count];

        // Step 2: Calculate the terms one by one.
        for (int index = 0; index < count; index++) {
            if (index < 1) {
                // Step 3: The first 1 terms are given. The first Catalan number is 1.
                terms[index] = 1;
            } else {
                // Step 4: Every other term comes from earlier terms. Apply the Catalan rule from the statement.
                terms[index] = terms[index - 1] * 2 * (2 * index - 1) / (index + 1);
            }
        }

        // Step 5: Print all terms on one line, separated by a space.
        StringBuilder line = new StringBuilder();
        for (int index = 0; index < count; index++) {
            if (index > 0) {
                line.append(" ");
            }
            line.append(terms[index]);
        }
        System.out.println(line);
    }
}