menu

[LeetCode] 007. Reverse Integer

Problem (Easy）

007. Reverse Integer

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

  • Input: 123
  • Output: 321

Example 2:

  • Input: -123
  • Output: -321

Example 3:

  • Input: 120
  • Output: 21

Note: Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: $[−2^{31}, 2^{31} − 1]$. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

Approach 1: Manipulate Strings

Idea

Manipulate the number as string, which is easy to reverse. Then cast integer type to the reversed string.

Solution

class Solution1:
    def reverse(self, x: int) -> int:
        l = str(x).split('-')
        if len(l) > 1:
            sign = '-'
        else:
            sign = ''
        rev = l[-1][::-1]
        while rev[0] == '0' and  len(rev) > 1:
            rev = rev[1:]

        res = int(''.join([sign, rev]))
        if ret > pow(2, 31)-1 or ret < -pow(2, 31):
            return 0
        return ret

Complexity

  • Time: $O(\log(x))$
  • Space: $O(1)$?

Approach 1 Update

Hint

  • int('00012') -> 12

Solution

class Solution1_update:
    def reverse(self, x: int) -> int:
        rev = str(abs(x))[::-1]
        sign = '' if x > 0 else '-' 
        ret = int(''.join([sign, rev]))
        if ret > pow(2, 31)-1 or ret < -pow(2, 31):
            return 0
        return ret

Approach 2

Idea

Numeric manipulation: reverse the number digit by digit from right. Basic procedure:

  1. Get the rightmost digit by digit = x % 10;
  2. Save the right most digit to ret += digit;
  3. Remove this rightmost digit from x by x //= 10;
  4. In the next loop, let the x’s digit to left by one bit by ret *= 10;
  5. Loop until x reaches 0.

Solution

class Solution2:
    def reverse(self, x: int) -> int:
        n = x if x > 0 else -x
        ret = 0
        while n != 0:
            ret *= 10
            ret += n % 10 
            n //= 10 
        ret = ret if x > 0 else -ret

        if ret > pow(2, 31)-1 or ret < -pow(2, 31):
            return 0
        return ret

Complexity

  • Time: $O(\log(x))$
  • Space: $O(1)$?



KF

Comments