Welcome to Subscribe On Youtube

7. Reverse Integer

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 [-231, 231 - 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:

• -231 <= x <= 231 - 1

Solutions

Solution 1: Mathematics

Let’s denote $mi$ and $mx$ as $-2^{31}$ and $2^{31} - 1$ respectively, then the reverse result of $x$, $ans$, needs to satisfy $mi \le ans \le mx$.

We can continuously take the remainder of $x$ to get the last digit $y$ of $x$, and add $y$ to the end of $ans$. Before adding $y$, we need to check if $ans$ overflows. That is, check whether $ans \times 10 + y$ is within the range $[mi, mx]$.

If $x \gt 0$, it needs to satisfy $ans \times 10 + y \leq mx$, that is, $ans \times 10 + y \leq \left \lfloor \frac{mx}{10} \right \rfloor \times 10 + 7$. Rearranging gives $(ans - \left \lfloor \frac{mx}{10} \right \rfloor) \times 10 \leq 7 - y$.

Next, we discuss the conditions for the inequality to hold:

• When $ans \lt \left \lfloor \frac{mx}{10} \right \rfloor$, the inequality obviously holds;
• When $ans = \left \lfloor \frac{mx}{10} \right \rfloor$, the necessary and sufficient condition for the inequality to hold is $y \leq 7$. If $ans = \left \lfloor \frac{mx}{10} \right \rfloor$ and we can still add numbers, it means that the number is at the highest digit, that is, $y$ must not exceed $2$, therefore, the inequality must hold;
• When $ans \gt \left \lfloor \frac{mx}{10} \right \rfloor$, the inequality obviously does not hold.

In summary, when $x \gt 0$, the necessary and sufficient condition for the inequality to hold is $ans \leq \left \lfloor \frac{mx}{10} \right \rfloor$.

Similarly, when $x \lt 0$, the necessary and sufficient condition for the inequality to hold is $ans \geq \left \lfloor \frac{mi}{10} \right \rfloor$.

Therefore, we can check whether $ans$ overflows by checking whether $ans$ is within the range $[\left \lfloor \frac{mi}{10} \right \rfloor, \left \lfloor \frac{mx}{10} \right \rfloor]$. If it overflows, return $0$. Otherwise, add $y$ to the end of $ans$, and then remove the last digit of $x$, that is, $x \gets \left \lfloor \frac{x}{10} \right \rfloor$.

The time complexity is $O(\log |x|)$, where $|x|$ is the absolute value of $x$. The space complexity is $O(1)$.

• Java
• C++
• Python
• Go
• Javascript
• C#
• RenderScript
• Php

• class Solution {
      public int reverse(int x) {
          int ans = 0;
          for (; x != 0; x /= 10) {
              if (ans < Integer.MIN_VALUE / 10 || ans > Integer.MAX_VALUE / 10) {
                  return 0;
              }
              ans = ans * 10 + x % 10;
          }
          return ans;
      }
  }
  

• class Solution {
  public:
      int reverse(int x) {
          int ans = 0;
          for (; x; x /= 10) {
              if (ans < INT_MIN / 10 || ans > INT_MAX / 10) {
                  return 0;
              }
              ans = ans * 10 + x % 10;
          }
          return ans;
      }
  };
  

• class Solution:
      def reverse(self, x: int) -> int:
          ans = 0
          mi, mx = -(2**31), 2**31 - 1
          while x:
              if ans < mi // 10 + 1 or ans > mx // 10:
                  return 0
              y = x % 10
              if x < 0 and y > 0:
                  y -= 10
              ans = ans * 10 + y
              x = (x - y) // 10
          return ans
  
  

• func reverse(x int) (ans int) {
  	for ; x != 0; x /= 10 {
  		if ans < math.MinInt32/10 || ans > math.MaxInt32/10 {
  			return 0
  		}
  		ans = ans*10 + x%10
  	}
  	return
  }
  

• /**
   * @param {number} x
   * @return {number}
   */
  var reverse = function (x) {
      const mi = -(2 ** 31);
      const mx = 2 ** 31 - 1;
      let ans = 0;
      for (; x != 0; x = ~~(x / 10)) {
          if (ans < ~~(mi / 10) || ans > ~~(mx / 10)) {
              return 0;
          }
          ans = ans * 10 + (x % 10);
      }
      return ans;
  };
  
  

• public class Solution {
      public int Reverse(int x) {
          int ans = 0;
          for (; x != 0; x /= 10) {
              if (ans < int.MinValue / 10 || ans > int.MaxValue / 10) {
                  return 0;
              }
              ans = ans * 10 + x % 10;
          }
          return ans;
      }
  }
  

• impl Solution {
      pub fn reverse(mut x: i32) -> i32 {
          let is_minus = x < 0;
          match x.abs().to_string().chars().rev().collect::<String>().parse::<i32>() {
              Ok(x) => x * (if is_minus { -1 } else { 1 }),
              Err(_) => 0,
          }
      }
  }
  
  

• class Solution {
      /**
       * @param int $x
       * @return int
       */
  
      function reverse($x) {
          $isNegative = $x < 0;
          $x = abs($x);
  
          $reversed = 0;
  
          while ($x > 0) {
              $reversed = $reversed * 10 + ($x % 10);
              $x = (int) ($x / 10);
          }
  
          if ($isNegative) {
              $reversed *= -1;
          }
          if ($reversed < -pow(2, 31) || $reversed > pow(2, 31) - 1) {
              return 0;
          }
  
          return $reversed;
      }
  }
  
  

All Problems

All Solutions