Print Integers in a Pyramid

I need to write a method that will print the integers from [1, maxValue] in a pyramid where the nth row contains n numbers like so (for printChart(24)):

1
2 3
4 5 6
7 8 9 10
11 12 13 14 15
16 17 18 19 20 21
22 23 24


I am wondering if there is a way to optimize my code for functionality, simplicity, or computational complexity (although I doubt the latter, because I think this runs at $$\O(n)\$$ time).

It has one helper function, which returns a boolean value representing whether or not a given integer, n, is a perfect square.

public boolean isPerfectSquare(int n){
int root = (int) Math.sqrt(n);
return root * root == n;
}

public void printChart(int maxValue) {
int number = 1;
while (number <= maxValue) {

System.out.print(number + " ");

/* A number n can be determined to be triangular iff
8n+1 is a perfect square;  if n is a triangular number,
print a line after it*/
if(isPerfectSquare(8*number+1)) { System.out.println(); }

number++;
}
}

• Your example is misleading, the sixth row contains 9 numbers. – Martin R Sep 1 '19 at 6:45
• Hello, I executed your code, and numbers 22, 23, 24 appear below the last row that ends with number 21. – dariosicily Sep 1 '19 at 8:03

2 Answers

You're doing things quite the hard way. You don't need to call sqrt, or determine perfect squares at all. Simply track y, and as soon as the row's x == y, make a newline, increment y and set x = 0.

The following examples show different results from what you've described:

import java.io.StringWriter;
import java.lang.Math;

class Pyramid {
interface ChartMethod {
abstract void run(int n);
}

static boolean isPerfectSquare(int n){
int root = (int) Math.sqrt(n);
return root * root == n;
}

static void chart_squares(int maxValue) {
int number = 1;
while (number <= maxValue) {
System.out.print(number + " ");

/* A number n can be determined to be triangular iff
8n+1 is a perfect square;  if n is a triangular number,
print a line after it*/
if (isPerfectSquare(8*number + 1))
System.out.println();
number++;
}

System.out.println();
}

static void chart_coords(int maxValue) {
int number = 1, y = 0, x = 0;
while (number <= maxValue) {
System.out.print(number + " ");

if (x == y) {
x = 0;
y++;
System.out.println();
}
else
x++;

number++;
}
System.out.println();
}

static void chart_coordloop(int maxValue) {
int number = 1;
for (int y = 0;; y++) {
for (int x = 0; x <= y; x++) {
System.out.print(number + " ");
if (number++ >= maxValue) {
System.out.println();
return;
}
}
System.out.println();
}
}

static void chart_incr(int maxValue) {
int increment = 2, next = 1;
for (int number = 1; number <= maxValue; number++) {
System.out.print(number + " ");
if (number == next) {
next += increment;
increment++;
System.out.println();
}
}
System.out.println();
}

static void chart_buf(int maxValue) {
StringWriter sw = new StringWriter();
int increment = 2, next = 1;
for (int number = 1; number <= maxValue; number++) {
sw.write(number + " ");
if (number == next) {
next += increment;
increment++;
sw.write('\n');
}
}
System.out.println(sw.toString());
}

static final ChartMethod[] methods = new ChartMethod[] {
Pyramid::chart_squares,
Pyramid::chart_coords,
Pyramid::chart_coordloop,
Pyramid::chart_incr,
Pyramid::chart_buf
};

static void test(ChartMethod method) {
method.run(7);
}

static void time(ChartMethod method) {
long start = System.nanoTime();
final int N = 200000;
method.run(N);
long dur = System.nanoTime() - start;

System.err.println(String.format("%.3f us", dur / 1e3 / N));
}

public static void main(String[] args) {
for (ChartMethod method: methods)
time(method);
}
}


This shows:

1.381 us
1.196 us
1.157 us
1.140 us
0.234 us


The most important thing is to buffer the output before writing.

• As I understand it, that does not work here. Could you possibly show an example code so I can better understand what you mean? – Matthew Anderson Sep 1 '19 at 1:36
• Edited. The only potential edge case is if the maximum number produces what would be a smaller row at the bottom. If, as your illustration shows, you need the bottom row to always be the widest, you'll need to add another clause to that if. – Reinderien Sep 1 '19 at 1:42
• actually still works in the edge case you mentioned. Weirdly enough, my slightly more complex method (which I would expect to take longer to run?) tends to take around .3 seconds fewer to perform the same 1000 operations than your method. Any idea why? – Matthew Anderson Sep 1 '19 at 2:04
• Tough to say. sqrt might be using a highly-efficient processor instruction that takes less time than the additional complexity of having more variables in the loop that are affected by conditional logic. – Reinderien Sep 1 '19 at 2:09
• So in my test, sqrt came out last. – Reinderien Sep 1 '19 at 4:21

Not sure how using roots help you, but here is my solution to the porblem (a pyramid, n-th row has length of n):

EDIT: I assumed that if the number won't be a perfect pyramid (like 24) then print until the number. If you want to print the biggest pyramid possible it simplifies the code a bit.

public static String pyr(int n) { //n is the target num
String str = "";
int currNum = 1;
int rowLength = 1;
while (currNum <= n) {
for (int i = 0; i < rowLength; i++) {
if (currNum <= n) {
//we want to go until n (not the end of this line)
System.out.print(currNum + " ");
currNum++;
}
}
rowLength++;
System.out.println();
}
return str;
}