Why the output becomes negative when input is big? (Pascal's Triangle)


  • 0
    J
    import java.util.*;
    public class PascalTriangle {
    	public void/*List<List<Integer>>*/ generate(int numRows) {
    		List<List<Integer>> list = new ArrayList<List<Integer>>(numRows);
    		List<Integer> firstRow = new ArrayList<Integer>(Arrays.asList(1));
    		if (numRows == 0){	
    		}else if (numRows == 1){
    			list.add(firstRow);
    		}else {                              // numRows > 1
    			list.add(firstRow);
    			for (int i = 2; i <= numRows; i++){
    				list.add(new ArrayList<Integer>());   //add a new ArrayList at i-th row.
    				list.get(i-1).add(1);
    				for (int j = 0; j <= i-3; j++){
    					int sum = list.get(i-2).get(j) + list.get(i-2).get(j+1);
    					list.get(i-1).add(sum);
    				}
    				list.get(i-1).add(1);
    			}
    		}
    		//return list;
    		System.out.println(list.get(numRows-1));	
    	}
    	public static void main(String[] args){
    		PascalTriangle pt = new PascalTriangle();
    		pt.generate(40);
    	}
    }
    

    My code has been accepted, but when I try to print the output out with large input number. I found there are some negative numbers.

    [1, 39, 741, 9139, 82251, 575757, 3262623, 15380937, 61523748, 211915132, 635745396, 1676056044, -384169860, -467509148, -2095364788, -628963116, -943444674, -518489742, -2065365450, 203787674, 203787674, -2065365450, -518489742, -943444674, -628963116, -2095364788, -467509148, -384169860, 1676056044, 635745396, 211915132, 61523748, 15380937, 3262623, 575757, 82251, 9139, 741, 39, 1]


  • 1
    J

    There must be integer overflows. The m-th number of the n-th row (counting from 0) is C(n,m) = n! / (m! * (n-m)!) where n! = n*(n-1)*(n-2)*…3*2*1 (also called factorial n), it is a number too big to be hold by an Integer if n > 12. So C(n,m) might got too large.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.