[leetcode] 7. Reverse Integer

Table of Contents

Description

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-2^31, 2^31 - 1], then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

Example 1:

Input: x = 123
Output: 321

Example 2:

Input: x = -123
Output: -321

Example 3:

Input: x = 120
Output: 21

Constraints:

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

Approach

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

If we ignore the above description, we can easily reverse the integer by converting it to a string, reversing the string, and converting it back to an integer in JavaScript.

/**
 * @param {number} x
 * @return {number}
 */
var reverse = function (x) {
  const absX = Math.abs(x);
  const reverseX = Number(absX.toString().split("").reverse().join(""));

  return reverseX >= Math.pow(2, 31) ? 0 : x < 0 ? -reverseX : +reverseX;
};

However, the above solution does not meet the problem’s description. Therefore, we cannot reverse the integer by simply reversing the string.

Instead, we can reverse the integer by repeatedly dividing it by 10 and taking the remainder. We then multiply the reversed integer by 10 and add the remainder to it, while simultaneously checking if it exceeds the 32-bit signed integer range.

Solution

/**
 * @param {number} x
 * @return {number}
 */
var reverse = function (x) {
  const BASE = 10;
  const MAX_INT = Math.pow(2, 31);
  let absX = Math.abs(x);
  let reverseX = 0;

  while (absX > 0) {
    const remainder = absX % BASE;

    // Check for overflow before updating the reverseX
    if (remainder > MAX_INT - reverseX * BASE) {
      return 0;
    }

    reverseX = reverseX * BASE + remainder;
    absX = Math.floor(absX / BASE);
  }

  return x < 0 ? -reverseX : +reverseX;
};

Complexity Analysis

Time Complexity

The time complexity is O(log(x)) because we divide the integer by 10 in each iteration.

Space Complexity

The space complexity is O(1) because we use a constant amount of space.