Why is an intermediate result cast to long before it is assigned to an int?

Question

In many of the coding streams and solutions in Codeforces and Codechef I have seen that when the number is bit large and we need to assign it to int then instead of casting it to int we cast it to long

int maxAreaOfCake(int h, int w, vector<int>& hCuts, vector<int>& vCuts)
{
    hCuts.push_back(0);
    hCuts.push_back(h);

    vCuts.push_back(0);
    vCuts.push_back(w);

    int MOD = 100000007;

    sort(hCuts.begin(), hCuts.end());
    sort(vCuts.begin(), vCuts.end());

    int horizontal = 0;
    for(int i = 0; i < (int)hCuts.size() - 1; i++) horizontal = max(horizontal, hCuts[i+1] - hCuts[i]);
    

    int vertical = 0;
    for(int i = 0; i < (int)vCuts.size() - 1; i++) vertical = max(vertical, vCuts[i+1] - vCuts[i]);
    
    return (int) ((long)horizontal%MOD * (long)vertical%MOD)%MOD;
}

It is the solution of MaxAreaOfCake question in leetcode. Here as the return type is int finally we are converting to int but before doing that we are first converting it to long. when i try to change the long to int i am getting the runtime error. If any one knows the answer please do share :)

Answer 1

The line in question is

return (int) ((long)horizontal%MOD * (long)vertical%MOD)%MOD;

The casts to long make sure that the expression (long)horizontal%MOD * (long)vertical%MOD is a multiplication of two long values. C and C++ compute the result of arithmetic operations as the "largest" type of their operands; if you multiply two ints, the result is intas well. If the mathematical result is too large for an int, that results in a signed overflow which is undefined behavior. That would happen here if horizontal%MOD * vertical%MOD were larger than the largest int, for example because the operands are larger than the square root of the maximum int value. In order to prevent that the code casts the operands to long, in the hopes that long's value range is larger (which may or may not be true). If it is true the result will typically always fit into a long (because typically the maximum int is smaller than the square root of the largest long). The result of the multiplication is then used to compute its modulo MOD, which is never larger than MOD-1 and hence smaller than the maximum int. It is therefore safe to cast the end result back to int, which is what the first (int) does. But the large intermediate result, before the final modulo, must be computed in a larger value range type.

Looking at circumstances one would have to perform in order to make this logic robust (if long and int have the same value range, the casts are futile) I wish there were a template in std::numeric_limits<T> like bool would_overflow(T2 arg) that for every arg of type T2 returns whether that value is convertible to T without overflowing.