Signed Integer Overflow[C++]

Question

Objective Find minimum value in stack in O(1) time complexity.

Issue : Failing at the below operation (2*x-minEle) in some Leetcode testcases.

Actual Error - runtime error: signed integer overflow: 2 * -2147483648 cannot be represented in type 'int'

I tried replacing every integer value with long long datatype but still getting the same error

Following is the code:

class MinStack {
public:
    int minEle = INT_MAX;
    vector<int> s;
    void push(int x) {
        if(s.empty())
        {
            minEle=x;
            s.push_back(x);
            return;
        }
        if(x<minEle)
        {
            s.push_back(2*x-minEle);
            minEle = x;
        }
        else
            s.push_back(x);    
    }
    
    void pop() {
        int y = s.back();
        if(y<minEle)
        {
            minEle = 2*minEle - y;
        }
        s.pop_back();
    }
    
    int top() {
        return s.back();
    }
    
    int getMin() {
        return minEle;
    }
};

What do you hope to learn from these contest/challenge/competitive coding/hacking sites? If it's to learn C++, you won't learn anything there. Like in this case, the correct solution is based on a mathematical or a programming trick. If you don't know what the trick is and attempt to code a brute-force approach, the program either runs slow, or fails to handle an obscure edge case. If you're trying to learn C++, you won't learn anything from meaningless online contest sites [but only from a good C++ textbook](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). — Sam Varshavchik, Dec 03 '20 at 03:40
I disagree. Programming challenges can be fun, help you think about how algorithms work, and keep you motivated to make progress. Many people do not learn best from books, but through experience (ideally paired with a book for a theoretical grounding). — Tumbleweed53, Dec 03 '20 at 04:58
The opinions about competitive programming sites aside ..... in this case, the flaw in question can be easily triggered with `int main() {MinStack x; x.push(0); x.push(INT_MIN);}`. Work out how to adjust the code to work correctly in this case, and you will address that problem. I offer no assurances that is the *only* flaw in the code though. — Peter, Dec 03 '20 at 08:59

score 0 · Answer 1 · answered Dec 11 '20 at 06:32

0

I also face the same problem on a programming challenge site but didn't encounter an "integer overflow" on IDE. "long long" data type works for me on IDE.

answered Dec 11 '20 at 06:32

Bhupesh Kumar

1
1

Amit Pandey · Answer 2 · 2023-01-21T20:46:26.520

As per my understanding, your x is int when you multiply INT_MIN * 2 it goes out of the range of int. as int * int results in int. so changing data type of x to long long int might solve the issue. Just look at the code I am posting below with some modification.

class MinStack {
    stack<long long int> s;
    long long int mini;
public:
    MinStack() {
        mini = INT_MAX;
    }
    
    void push(int val) {
        long long nval = val;
        if (s.empty()) {
            mini = nval;
            s.push(nval);
            return;
        }
        else if (nval < mini) {
            s.push(2 * nval - mini);
            mini = nval;
        }

        else
            s.push(nval);
    }
    

};

Signed Integer Overflow[C++]

2 Answers2