Shouldn't we also consider corner cases where INT_MIN and INT_MAX are involved?


  • 7
    S

    I noticed that OJ currently does not have test cases which involves extreme integer values, i.e. INT_MIN/INT_MAX. For instance, the following code:

    vector<string> res;
    char buf[50];
    void addMissingRange(int left, int right, bool inc_left = false, bool inc_right = false)
    {
        if (right < left) return; // The range does not exist
        else if (right == left) sprintf(buf, "%d", left); // The range has only one element
        else sprintf(buf, "%d->%d", left, right); // A two element range
        
        res.push_back(buf);
    }
    
    vector<string> findMissingRanges(int A[], int n, int lower, int upper) {
        int last = lower-1;
        for (int i = 0; i < n; ++i)
        {
            addMissingRange(last+1, A[i]-1);
            last = A[i];
        }
        addMissingRange(last+1, upper); // Add the last range.
        return res;
    }
    

    would pass OJ, but as a matter of fact, it fails on inputs like this:

    A = [INT_MAX]; lower = 0, upper = INT_MAX;
    

    The expected output should be: ["0->2147483646"],

    but the actual output produced by the code above is: ["0->2147483646", "-2147483648->2147483647"]

    It is because 'last+1' in the second last row overflows to INT_MIN, thus creating a giant range between 'last' and 'upper'.

    So my questions are:

    1. Do you guys think that we should add those corner cases to OJ?

    2. If I would like to make sure my code works for ALL possible inputs, is there any elegant trick that I can use to avoid the overflow problem?

    Thanks.


  • 0
    W

    good finding, should consider this case!


  • 0

    @stellari Thanks, I have added your test case. I think the answer is yes, we should consider corner cases like these.


  • 0
    Z

    @1337c0d3r

    Some more corner case should be added.
    Like,
    Test case 1:
    A = []
    lower = -2147483648
    upper = 2147483647
    Test case 2:
    A = []
    lower = 0
    upper = 2147483647
    Test case 3:
    A = [-2147483648]
    lower = -2147483648
    upper = 2147483647
    ...


  • 0

    @zhugexubin Thanks, I have added your test cases.


  • 0
    L

    So the question is, how to adjust the code in order these corner test case? I found that current highest voted answer doesn't pass OJ anymore.
    Happy new year!


  • 0

    @lzjknight said in Shouldn't we also consider corner cases where INT_MIN and INT_MAX are involved?:

    So the question is, how to adjust the code in order these corner test case? I found that current highest voted answer doesn't pass OJ anymore.
    Happy new year!

    Have seen someone solve this by converting integer to long :D


  • 0
    Q
    This post is deleted!

  • 0
    D
    vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
        vector<string> vs;
        if(nums.empty())
        {
            string tmp = to_string(lower);
            if(upper > lower)
                tmp += "->" + to_string(upper);
            vs.push_back(tmp);
            return vs;
        }
        if(lower < nums[0])
        {
            string tmp = to_string(lower);
            if(nums[0] - 1 > lower)
                tmp += "->" + to_string(nums[0] - 1);
            vs.push_back(tmp);               
        }
        for (int i = 1; i < nums.size(); i++)
        {
            if(nums[i-1] != INT_MAX && nums[i] > nums[i-1] + 1)
            {
                string tmp = to_string(nums[i-1]+1);
                if(nums[i] - 1 != nums[i-1] + 1)
                    tmp += "->" + to_string(nums[i] - 1);
                vs.push_back(tmp);               
            }
        }
        if(upper > nums[nums.size() -1])
        {
            string tmp = to_string(nums[nums.size()-1] + 1);
            if(upper > nums[nums.size()-1] + 1)
                tmp += "->" + to_string(upper);
            vs.push_back(tmp);            
        }
        return vs;
    }

  • 0
    D

    The above code passed all latest test cases.


Log in to reply
 

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