Reverse Integer

Difficulty: Medium

You're given a signed 32-bit integer. Reverse the order of its decimal digits, keeping its original sign.

If reversing the digits would produce a number too large or too small to fit in a signed 32-bit integer (the same range a 32-bit int can hold in many languages: from -2^31 to 2^31 - 1), return 0 instead of the reversed value.

Examples

Input: x = 123
Output: 321

Input: x = -123
Output: -321

The digits reverse the same way; the sign is kept as-is.

Input: x = 1534236469
Output: 0

Reversed, this would be 9646324351, which is larger than the maximum signed 32-bit value (2147483647) - so 0 is returned instead.

Constraints

-2^31 <= x <= 2^31 - 1

Approach

The direct way to reverse the digits is to convert the number to a string (keeping track of its sign separately), reverse the string, and parse the reversed string back into a number - then compare that result against the signed 32-bit range to decide whether to return 0.

The more careful approach reverses the digits with pure arithmetic instead of ever touching a string: repeatedly peel the last digit off x using % 10, and remove it from x using integer division by 10, building up the reversed result one digit at a time. The one detail that needs real care is the overflow check - instead of waiting until after the number might have already overflowed, this approach checks, before every multiply-and-add step, whether adding the next digit would push the result past the maximum or minimum allowed value, and bails out to 0 immediately if it would.

Solutions

Brute Force - Reverse via String Conversion

Convert the absolute value of x to a string, reverse the string, parse it back into a number, and reapply the original sign. Then check whether the result fits inside the signed 32-bit range.

function reverse(x) {
  const sign = x < 0 ? -1 : 1;
  const reversed = Math.abs(x).toString().split("").reverse().join("");
  const result = sign * Number(reversed);

  const INT_MAX = 2 ** 31 - 1;
  const INT_MIN = -(2 ** 31);

  if (result > INT_MAX || result < INT_MIN) return 0;
  return result;
}

Time: O(d), where d is the number of digits in x · Space: O(d), for the string representation

Optimal - Build the Reversed Number Digit by Digit, Checking Overflow Early

Peel digits off x one at a time using % 10 and integer division by 10, building the reversed result with ordinary arithmetic. Before adding each new digit, check whether doing so would push the result past the signed 32-bit range, and return 0 immediately if it would - rather than letting it overflow first.

function reverse(x) {
  const INT_MAX = 2 ** 31 - 1;
  const INT_MIN = -(2 ** 31);

  let result = 0;
  while (x !== 0) {
    const digit = x % 10; // keeps the sign of x automatically in JS
    x = Math.trunc(x / 10);

    if (
      result > Math.trunc(INT_MAX / 10) ||
      (result === Math.trunc(INT_MAX / 10) && digit > 7)
    ) {
      return 0;
    }
    if (
      result < Math.trunc(INT_MIN / 10) ||
      (result === Math.trunc(INT_MIN / 10) && digit < -8)
    ) {
      return 0;
    }

    result = result * 10 + digit;
  }

  return result;
}

Time: O(d), where d is the number of digits in x · Space: O(1)