Pascals Triangle in Following Code Does Not Get Correct Result When Input Parameters are Big

29 Views Asked by At

A nCr problem is calculated using the following code. For small input numbers, the results are correct. But when n=200 and r=100, its result is 114908264. The result should be 407336795.

What is wrong here?

Integer ncr(Integer n, Integer r) {
    if(n<r)
        return 0;
    long[] arr=new long[n+1];
    
    arr[0]=1l;
    for(int i=1; i<=n; i++){
        for(int j=i; j>0; j--){
            arr[j]+=arr[j-1];
        }
    }
    
    return (int)arr[r];
}

Edit: Using BigInteger class has the same issue.

Integer ncr(Integer n, Integer r) {
    if(n<r)
        return 0;
    BigInteger[] arr=new BigInteger[n+1];
    
    arr[0]=BigInteger.valueOf(1);
    for(int i=1; i<=n; i++){
        for(int j=i; j>0; j--){
            if(arr[j]==null)
                arr[j]=BigInteger.ZERO;
            arr[j]=arr[j].add(arr[j-1]);
        }
    }
    
    return arr[r].intValue();
}

Edit- The function should return BigInteger, not Integer. See @leogtzr's code.

0

There are 0 best solutions below