How to solve Pascal triangle loop fails issue?

Question

I'm facing an error on my Pascal triangle, but I don't know whether it's Java or my code which is the problem. Here is the code:

import java.util.Scanner;

public class sdz {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int levels;
        levels = sc.nextInt();

        for(int i = 0; i <= levels; i++){
            for(int j =0; j <= i; j++){
                System.out.print(combinatorial(i,j) + " ");
            }

            System.out.println();

        }
    }
    static int fact(int n ){
        if(n > 0)
            return n * fact(n-1);
        else
            return 1;
    }

    static int combinatorial(int n , int r){

        return fact(n)/(fact(r) * fact(n-r));
    }

}

When I input the level to 13, it fails. Here is the result:

The loop at 13

You should show the exact stack trace. Are you getting a stack overflow error, arithmetic overflow, or something else? — Tim Biegeleisen, Nov 07 '16 at 06:46
Your program is probably spinning then at level 13. Have a look at how dynamic programming can help to avoid the problem you are having. — Tim Biegeleisen, Nov 07 '16 at 06:56

score 2 · Accepted Answer · answered Nov 07 '16 at 07:08

This is caused by integer overflow issue. The result of fact(13) is 6227020800, which is larger than what fits in an integer.

Either use long (which would only delay the issue), BigInteger or define a combinatorial object. And use dynamic programming principles to avoid repetitive calculation, as shown by @Kaidul

Kaidul · Answer 2 · 2016-11-07T08:15:21.500

1

I don't know if its an integer overflow or anything else. Can we write the solution with less hassle?

public static void pascalTriangle(int levels) {

        for (int i = 0; i <= levels; i++) {
            List<Integer> row = new ArrayList<>();
            int s = 1;
            for (int j = 0; j <= i; j++) {
                row.add(s);
                s = s * (i - j) / (j + 1);
            }
            System.out.println(row);
        }

}

Here I've used the formula of binomial coefficient nCr+1 = nCr * (n -r) / (r + 1). I am using the already calculated result nCr to avoid repetitive calculation.

In your version, you calculated factorial from scratch every time. Perhaps using memorization would be useful.

Edit

Moreover you don't actually need to do any combinatoric stuffs to calculate pascal triangle. You can simply do some addition on previous level to get current level.

public static void pascalTriangle(int levels) {

    if (levels == 0) return;

    List<Integer> currList = new ArrayList<>();

    System.out.println("1");

    for (int i = 2; i <= levels; i++) {
        List<Integer> prevList = new ArrayList<>(currList);
        currList.clear(); 
        currList.add(1);
        for (int j = 0, k = 1; k < prevList.size(); j++, k++) {
            currList.add(prevList.get(j) + prevList.get(k));
        }
        currList.add(1);
        System.out.println(currList);
    }
}

edited Nov 07 '16 at 08:15

answered Nov 07 '16 at 06:44

Kaidul

15,409
15
81
150

When you are coding for pascal triangle, why even use multiplication at all? This is not how you write code for Pascal Triangle. Bad example – vish4071 Nov 07 '16 at 06:57
@vish4071 yes, you're right. I've just showed a improved version of his code. Check the update. I've added a simpler version you intended. – Kaidul Nov 07 '16 at 07:04
Yeah...thats what I'm talking about :) Though this can be done in a little less LOC, this is fine – vish4071 Nov 07 '16 at 07:04
Yes, true. Check now, I've reduced the size a bit. – Kaidul Nov 07 '16 at 07:18
In the addition variant, you should merge the `levels > 1` case into the following loop. The `prevList` should only be declared inside the loop. And don't mix `i++` and `++i` unless it is really necessary. – Roland Illig Nov 07 '16 at 07:22
@RolandIllig I've edited the code as you suggested. Thanks! – Kaidul Nov 07 '16 at 08:07

How to solve Pascal triangle loop fails issue?

2 Answers2

Edit