Overflow check and Proof in 10 lines


  • 0
    G
      /* Without using 'long' */
      // A couple of notes to understand this solution:
      // (1) Since c++11, 'x/10' guaranteed truncate towards 0, for both +/- int.
      // (2) Naively, for 'x = y*10 + z'; we need to check for two overflow conditions:
      //        ov(1). '*10' overflow
      //        ov(2). '+ z' overflow
      //     However, for this problem, ov(2) is impossible 
      int32_t reverse(int32_t x) {
        int32_t tmp, result=0;
        while (x) {
          tmp = result * 10;
          if (tmp/10 != result)  // check for '*' overflow
            return 0;
          // tmp += x % 10;      // check for '+' overflow
          // if ((tmp < 0 && result > 0) || (tmp > 0 && result < 0)) 
          //   return 0;
          result = tmp + x % 10; // '+' never overflow here. Proof for positive x:
          x /= 10;     // INT32_MAX = 2147483647, 'tmp' must be <= 214748364.0 * 10
        }              // Assuming '+' did overflow, then (x % 10) must be (8 or 9), 
        return result; // which is impossible, because 'x' would be (8|9)7463847412.
      }
    

Log in to reply
 

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