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.