# (JAVA)Binomial Coefficients without overflow

• May not be the best idea, but a straight thinking is to calculate binomial coefficients.
e.g: input 4, the answer is 1, 4, 6, 4, 1 came from C(4,0) C(4,1) ... C(4, 4)

I try to write a method to calculate binomial coefficients but it easily overflows. Hereby the final acceptted version.

``````public class Solution {
public List<Integer> getRow(int rowIndex) {
List<Integer> res = new ArrayList<Integer>();
for (int i = 0; i <= rowIndex; i++) res.add((int)BC(rowIndex, i));
return res;
}

public long BC(int n, int m) {
long res = 1;
int large = Math.max(n - m, m), small = Math.min(n - m, m);
for (int i = n; i > large; i--) {
res *= i;
res /= small - (i - large) + 1;
}
return res;
}
}
``````

explaination:

• We cannot just calculate factors and divide them in generating results, because it is too easy to get overflowed even using long.
• Thus we need to calculate BC straightly.
• C(a, b) = a! / (b! * (a - b)!)
• define large and small as larger and smaller number in b and (a - b), thus C(a, b) = a! / (large! * small!)
• then calculate multiplications in C(a, b) decreasingly:
a * a - 1 * ... * large + 1
• at the same time calculate the left divisions increasingly:
/1 /2 /.../small
• multiplications and divisions must in same iteration or multiplications will lead to overflow. divisions must be increasingly or sometimes it is not divisible.
(e.g: C(5,2) - large = 3, small = 2.
C(5,2) = (5 * 4) / 2 / 1
the correct calculation is (5 / 1) * (4 / 2) = 10
if divide 2 at first, (5 / 2) * (4 / 1) = 8

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