Einstein - 1 year ago 131
Java Question

# 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.

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 `BigInteger`s 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" : " "));
}
}
}
``````