2
\$\begingroup\$

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++;
    }
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Your example is misleading, the sixth row contains 9 numbers. \$\endgroup\$ – Martin R Sep 1 at 6:45
  • 1
    \$\begingroup\$ Hello, I executed your code, and numbers 22, 23, 24 appear below the last row that ends with number 21. \$\endgroup\$ – dariosicily Sep 1 at 8:03
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ As I understand it, that does not work here. Could you possibly show an example code so I can better understand what you mean? \$\endgroup\$ – Matthew Anderson Sep 1 at 1:36
  • \$\begingroup\$ 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. \$\endgroup\$ – Reinderien Sep 1 at 1:42
  • \$\begingroup\$ 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? \$\endgroup\$ – Matthew Anderson Sep 1 at 2:04
  • \$\begingroup\$ 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. \$\endgroup\$ – Reinderien Sep 1 at 2:09
  • 1
    \$\begingroup\$ So in my test, sqrt came out last. \$\endgroup\$ – Reinderien Sep 1 at 4:21
0
\$\begingroup\$

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;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.