Pascal Triangle Integer Overflow when values need to be find at row 30

Question

This is Integer overflow problem but i am not able to wrap my head around it for using only Integer for solution [not using long ]. I want to know how can we test or form equation when overflow happens without moving to higher datatype?

Aim : try to find pascal triangle values at i index ;

rowIndex can be max 33.

Code:

class Solution {
    public List<Integer> getRow(int rowIndex) {
        
        List<Integer> pt = new ArrayList<>();
        
        int prev=1;
        int curr=1;
        int n=rowIndex+1;
        pt.add(prev);
        
        for (int i=1; i <= rowIndex; i++) {    
            
            curr = prev * (n-i)/i;
            
            pt.add(curr);
            
            prev=curr;
        }
        return pt;
        
    }

I solved it with adding previous row values in O(k) space. Your overflow seems to happen when you multiply. Make it long datatype, divide it and then store integer form. — nice_dev, Aug 12 '20 at 09:53
I am curious about how can we solve the integer overflow case. And what are measures to be taken if it happens in other problems ! I am trying few combination of mod but not working. — Deepak Negi, Aug 12 '20 at 10:00
You don't need mod, just change it to higher type and store the (int) of the results. — nice_dev, Aug 12 '20 at 10:13
See [How does Java handle integer underflows and overflows and how would you check for it? - Stack Overflow](https://stackoverflow.com/questions/3001836/how-does-java-handle-integer-underflows-and-overflows-and-how-would-you-check-fo#answer-3001879) — , Aug 12 '20 at 10:42

score 1 · Accepted Answer · 2020-08-12T13:30:08.533

You can prevent overflow by using long instead of int.

public List<Integer> getRow(int rowIndex) {
    
    List<Integer> pt = new ArrayList<>();
    
    int prev=1;
    int curr=1;
    int n=rowIndex+1;
    pt.add(prev);
    
    for (int i=1; i <= rowIndex; i++) {    
        
        curr = (int) ((long) prev * (n-i)/i);
        
        pt.add(curr);
        
        prev=curr;
    }
    return pt;
    
}

But the problem can be solved without using long. The prev * (n-i) part may overflow, but this product should be divisible by i. You can avoid the overflow by dividing before the multiplication. If you calculate GCD of (n-i) and i in advance, you can rewrite as follows.

        int gcd = gcd(n - i, i);
        curr = (prev / (i / gcd)) * ((n - i) / gcd);

GCD can be obtained by the following method.

static int gcd(int m, int n) {
    while (n > 0) {
        int r = m % n;
        m = n;
        n = r;
    }
    return m;
}

before:

[1, 30, 435, 4060, 27405, 142506, 593775, 2035800, 5852925, 14307150, 30045015, 54627300, 86493225, 119759850, 145422675, -131213633, -123012780, -101304642, -73164463, -46209134, -25415023, -12102391, -4950978, -1722079, -502273, -120545, -23181, -3434, -367, -25, 0]

after:

[1, 30, 435, 4060, 27405, 142506, 593775, 2035800, 5852925, 14307150, 30045015, 54627300, 86493225, 119759850, 145422675, 155117520, 145422675, 119759850, 86493225, 54627300, 30045015, 14307150, 5852925, 2035800, 593775, 142506, 27405, 4060, 435, 30, 1]

Thanks Ska, i did same .. but i was looking in the line of handling overflow with mod operation not with long. Still trying combination of modular maths to achieve it without long. — Deepak Negi, Aug 12 '20 at 11:38
@OldMonk I'm not sure what you mean by `mod operation`, but I added a way to solve the problem without using `long` to my answer. — , Aug 12 '20 at 12:26
thanks for the solution. Idea was to solve it without using long. gcd was trick :] — Deepak Negi, Aug 12 '20 at 12:56

Pascal Triangle Integer Overflow when values need to be find at row 30

1 Answers1