Floyd's Triangle

easy Pattern Printing

Problem

Read n and print Floyd's triangle with n rows. It is filled with the natural numbers 1, 2, 3, ... in order. Row i has i numbers.

Constraints

  • 1 <= n <= 20

Examples

Input

3

Output

1
2 3
4 5 6

Solutions

Best approachTime O(n^2)Space O(1)

The counter is declared outside the loops, so it keeps its value from one row to the next. Each row takes as many numbers as its row number.

Same code works in Java810172125Basic features only, so nothing changes between versions.

Java 8 has no String.repeat, so we use a small helper method. In Java 11 and newer you can write " ".repeat(count).

/*
 * Problem : Floyd's triangle.
 * Input   : One integer n (rows).
 * Output  : n lines of numbers.
 * Approach: Keep one counter that never resets.
 * Time    : O(n^2)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

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

        // Step 1: Make one counter that keeps growing. It starts at 1 and is never reset.
        int counter = 1;

        // Step 2: Repeat once for each row. Row numbers go from 1 to rows.
        for (int row = 1; row <= rows; row++) {
            StringBuilder line = new StringBuilder();

            // Step 3: Row i has i numbers. Take the next numbers from the counter.
            for (int position = 1; position <= row; position++) {
                if (position > 1) {
                    line.append(" ");
                }
                line.append(counter);
                counter++;
            }

            // Step 4: Print the finished line.
            System.out.println(line);
        }
    }
}
Hints (1)
  1. Where should the counter be created: inside or outside the row loop?