Triangular Numbers

beginner Series and Sequences

Problem

Read n and print the first n triangular numbers. The k-th triangular number is 1 + 2 + ... + k, which is the number of dots in a triangle with k rows: 1 3 6 10 15 ...

Constraints

  • 0 <= n <= 60

Examples

Input

6

Output

1 3 6 10 15 21

Solutions

Best approachTime O(n)Space O(n)

Each triangular number is the one before it plus the next natural number. For example 6 + 4 = 10.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Print the first n terms of the triangular 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 term is 1.
                terms[index] = 1;
            } else {
                // Step 4: Every other term comes from earlier terms. Add the next natural number (index + 1) to the previous term.
                terms[index] = terms[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);
    }
}
Hints (1)
  1. How much does each term grow? By 2, then 3, then 4, ...