Numbers become negative


  • 0
    E

    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;
        }
    };
    

    Submission Result: Wrong Answer

    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.


  • 1
    O

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


  • 1
    F

    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);
        }
        
    };

Log in to reply
 

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