# Numbers become negative

• My code uses the mathematics equation for Pascal's triangle:

``````class Solution {
public:
vector<vector<int> > generate(int numRows) {
vector<vector<int>> res;
if(numRows == 0) return res;
for(int i = 1;i <= numRows; i++){
vector<int> line;
for(int j = 1; j <= i; j++){
line.push_back(pascal(i,j));
}
res.push_back(line);
}
return res;
}
int pascal(int i, int j){
if(j == 1 || j == i) return 1;
if(j >= i/2+1) j = i-j+1;
int val = 1;
int m = 1;
for(int k = 1; k < j; k++){
val = val*(i-k);
m = m*k;
}
val = val/m;
return val;
}
};
``````

Input: 20

All the previous lines match the expected results expect line 19 and 20.

Expected:
[1,18,153,816,3060,8568,18564,31824,43758,48620,43758,31824,18564,8568,3060,816,153,18,1]
[1,19,171,969,3876,11628,27132,50388,75582,92378,92378,75582,50388,27132,11628,3876,969,171,19,1]

My output：
[1,18,153,816,3060,8568,18564,31824,43758,1276,43758,31824,18564,8568,3060,816,153,18,1]
[1,19,171,969,3876,11628,27132,50388,-30940,-2308,-2308,-30940,50388,27132,11628,3876,969,171,19,1]

Why the numbers become negative when they are large? They are definitely inside the int range.

• It is simply because val and m in the function pascal might overflow. The product of integers from 10 to 20 is very big.

• This is how I dealt with long numbers and I hope my code is readable if not efficient. I solved in a similar way using combinatorics [i.e. Binomial Coefficients ]

``````class Solution {
public:
vector<vector<int> > generate(int numRows) {
vector<vector<int> > triangle;
for (int i = 0; i < numRows; ++i) {
vector<int> row;
for (int j = 0; j <= i; ++j) {
row.push_back(ncr(i,j));
}
triangle.push_back(row);
}
return triangle;
}
int ncr(int n, int r) {
if (r == 0 || n == r) return 1;
if (r < n-r) r = n-r;
long long num, den;
num = den = 1;
for (int i = r+1; i <= n; ++i) num *= i;
for (int j = 2; j <= n-r; ++j) den *= j;
return (int) (num / den);
}

};``````

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