X Shape Star Pattern

medium Pattern Printing

Problem

Read n and print an X made of stars inside an n by n square. A star is printed where the row equals the column, or where the position is on the other diagonal.

Constraints

  • 1 <= n <= 49

Examples

Input

3

Output

* *
 *
* *

Solutions

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

In a square the main diagonal has row == column and the other diagonal has row + column == size - 1. We print a star on either diagonal.

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 : X shape of stars.
 * Input   : One integer n (side length of the square).
 * Output  : n lines.
 * Approach: Check the two diagonals.
 * 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 size = new Scanner(System.in).nextInt();

        // Step 1: Repeat once for each row. Row numbers start at 0 and end at size - 1.
        for (int row = 0; row < size; row++) {
            // Step 2: Find the last column that has a star in this row. We stop there to avoid extra spaces.
            int lastColumn = Math.max(row, size - 1 - row);
            StringBuilder line = new StringBuilder();

            // Step 3: Visit the columns from 0 to the last star.
            for (int column = 0; column <= lastColumn; column++) {
                // Step 4: A star goes on the main diagonal (row = column) or the other diagonal (row + column = size - 1).
                if (row == column || row + column == size - 1) {
                    line.append("*");
                } else {
                    line.append(" ");
                }
            }

            // Step 5: Print the finished line.
            System.out.println(line);
        }
    }
}
Hints (2)
  1. Which positions are on the main diagonal?
  2. For the other diagonal, row plus column is always size minus 1.