Concentric Number Square

hard Pattern Printing

Problem

Read n and print an n by n square made of rings. The outer ring has the value n, the next ring inside has the value n-1, and so on. Separate the numbers in a row with one space.

Constraints

  • 1 <= n <= 20

Examples

Input

3

Output

3 3 3
3 2 3
3 3 3

Solutions

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

A cell on the outer border has distance 0 to a border. A cell one ring inside has distance 1, and so on. The value is n minus this distance. We find the distance with the smallest of four numbers.

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 : Square made of rings.
 * Input   : One integer n (side length).
 * Output  : n lines of n numbers.
 * Approach: Each cell depends on its distance to the nearest border.
 * 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.
        for (int row = 0; row < size; row++) {
            StringBuilder line = new StringBuilder();

            // Step 2: Visit each column of the row. Column numbers start at 0.
            for (int column = 0; column < size; column++) {
                // Step 3: Find the distance to the nearest border: top, left, bottom or right.
                int distance = Math.min(Math.min(row, column), Math.min(size - 1 - row, size - 1 - column));

                // Step 4: The border has the value n. Each ring inside has a value one smaller.
                int value = size - distance;

                if (column > 0) {
                    line.append(" ");
                }
                line.append(value);
            }

            // Step 5: Print the finished line.
            System.out.println(line);
        }
    }
}
Hints (2)
  1. How far is a cell from each of the four borders?
  2. Use the smallest distance.