Is there any chance that simplified forms of certain mathematical expressions throw overflow errors while complex ones dont?

Question

I was attempting the #69 problem of leetcode, which involves finding square root of given number.

I proceeded via a binary search approach.

int mySqrt(int x) {
    if (x==0 || x==1){
        return x;
    }
    int start =1;
    int end=x;
    int mid=-1;
    while(start<=end){
        mid=(end+start)/2;//the problem lies here
        long long square=static_cast<long long>(mid)*mid;
        if (square>x){
            end=mid-1;
        }
        else if(square==x){
            return mid;
        }
        else{
            start=mid+1;
        }
     }
     return static_cast<int>(round(end));
}

When I changed mid=start+(end-start)/2;the test cases ran fine, however it threw 'signed integer overflow' for x=2147483647, saying 'runtime error: signed integer overflow: 2147483647 + 1 cannot be represented in type 'int''.

Answer 1

To answer the question directly: yes, different expressions that are mathematically equivalent can produce distinct results in a program.

In this case, if you first add start and end, then divide by 2, if their sum is larger than INT_MAX, you get integer overflow. However, if you subtract start from end, there cannot be overflow as you are subtracting two positive numbers.

However, even this approach is not completely correct if the numbers might be negative. Prefer using std::midpoint (since C++ 20) from the <numeric> header instead to avoid these issues altogether.

#include <numeric>
// ...
mid = std::midpoint(start, end);