CODEWITHSUNDEEP
javaarraysalgorithmpascals-triangle
radholm
radholm

Reputation: 87

Pascal's triangle faulty output

Hi I'm making an iterative Pascal's triangle in Java. So far everything works great, until number of rows exceed 13. The output becomes faulty. I must be doing something wrong here, please help.

IterativePascal:

public class IterativePascal extends ErrorPascal implements Pascal {
    private int n;
    IterativePascal(int n) throws Exception {
        super(n);
        this.n = n;
    }
    public void printPascal() {
        printPascal(false);
    }

    public void printPascal(boolean upsideDown) {
        if (n == 0) { return; }
        for (int j = 0; j <= n; j++) {
            for (int i = 0; i < j; i++) {
                System.out.print(binom(j - 1, i) + (j == i + 1 ? "\n" : " "));
            }
        }
    }

    public long binom(int n, int k) {
        return (k == 0 || n == k) ? 1 : faculty(n) / (faculty(k) * faculty(n - k));
    }

    private long faculty(int n) {
        if (n == 0 || n == 1) { return 1; }
        int result = 1;
        for (int i = 2; i <= n; i++) {
            result = result * i;
        }
        return result;
    }
}

Output:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
1 11 55 165 330 462 462 330 165 55 11 1
1 12 66 220 495 792 924 792 495 220 66 12 1
1 4 24 88 221 399 532 532 399 221 88 24 4 1 <----- wrong
1 0 1 5 14 29 44 50 44 29 14 5 1 0 1 <----- wrong

Help would be appriciated, since I'm new with algorithms.

Upvotes: 2

Views: 151

Answers (2)

xenteros
xenteros

Reputation: 15842

You're reaching number overflow. Because 14! is too big to fill in java long.

The solution will be to use + instead of !.

Keep your triangle as an 2D array and iterate through it. Each cell should be sum of two 'above'.

+---+---+---+---+
| 1 |   |   |   |
| 1 | 1 |   |   |
| 1 | 2 | 1 |   |
| 1 | 3 | 3 | 1 |
+---+---+---+---+

The code will be as it follows:

public static void triangle(int n) {
    int[][] triangle = new int[n];
    for (int i = 0; i < n; i++) {
        triangle[i] = new int[i+1];
    }
    triangle[0][0] = 1;
    triangle[1][0] = 1;
    triangle[1][1] = 1;
    for (int i = 2; i < n; i++) {
        triangle[i][0] = 1;
        for (int j = 1; j < triangle[i].length - 1; j++) {
            triangle[i][j] = triangle[i-1][j] + triangle[i-1][j+1];
        }
        triangle[i][triangle[i].length-1] = 1;
    }
    printArray(triangle);
}

Edit:
As the OP requires recursive solution with binoms, I decided to add solution introducing BigIntegers as it might be the case.

public BigInteger binom(int n, int k) {
        return (k == 0 || n == k) ? BigInteger.ONE : faculty(n).divide((faculty(k).multiple(faculty(n - k)));
    }

private BigInteger faculty(int n) {
    BigInteger result = BigInteger.ONE;
    while (!n.equals(BigInteger.ZERO)) {
        result = result.multiply(n);
        n = n.subtract(BigInteger.ONE);
    }
    return result;
}

public void printPascal(boolean upsideDown) {
    if (n == 0) { return; }
    for (int j = 0; j <= n; j++) {
        for (int i = 0; i < j; i++) {
            System.out.print(binom(j - 1, i).toString() + (j == i + 1 ? "\n" : " "));
        }
    }
}

Upvotes: 6

asp
asp

Reputation: 172

Probably the problem is in your computation of the factorial: I'd assume that your int type can hold numbers up to 32 bits, but 13! is larger than that.

You could check whether long can store larger numbers and define result as long.

Upvotes: 0

Related Questions