Sdmg15 Sdmg15 - 1 month ago 17
Java Question

How to solve Pascal triangle loop fails issue?


  • 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's the result
The loop at 13

Answer

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