Print Integers in a Pyramid

Question

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++;
 }
}

• Martin R: Your example is misleading, the sixth row contains 9 numbers.
• dariosicily: Hello, I executed your code, and numbers 22, 23, 24 appear below the last row that ends with number 21.

Answer 1

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.

• Matthew Anderson: As I understand it, that does not work here. Could you possibly show an example code so I can better understand what you mean?
• Reinderien: 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.
• Matthew Anderson: 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?
• Reinderien: 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: So in my test, sqrt came out last.

Answer 2

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;
}