Solution by Ambition_Wang


  • 0
    A

    Approach #1 Integer Division [Accepted]

    Intuition

    each time we take least significant bit of x, and add it to reverse_sum.

    then we multiply reverse_num by 10, and continue doing above steps, finally we get reverse integer.

    e.g. 23

    Turn 1:

    x = 23

    • 3 is least significant bit of x
    • put 3 into reverse_num

    reverse_num = 3

    • divide x by 10

    Turn 2:

    x = 2

    • multiply reverse_num by 10

    reverse_num = 30

    • 2 is least significant bit of x
    • put 2 into reverse_num

    reverse_num = 30 + 2

    • divide x by 10

    x = 0

    Now:

    reverse_num = 32

    Algorithm

    1. create negative variable to handle negative case
      • ignore negative sign temporarily
      • compute result like positive number
      • adjust sign in the end
    2. propagate reverse_num and add least significant bit of x to reverse_num
    3. divide x by 10
    4. check overflow
    5. continue 2~4 until x is equal to 0
    6. give negative sign if necessary

    Python

    class Solution(object):
        def reverse(self, x):
            negative = True if x < 0 else False
            x = -x if negative else x
            reverse_num = 0
            while x != 0:
                reverse_num = reverse_num * 10 + x % 10
                x = int(x / 10)
                if abs(reverse_num) > (2 ** 31 - 1):
                    return 0
            reverse_num = -reverse_num if negative else reverse_num
            return reverse_num
    

    Complexity Analysis

    • Time complexity : $$O(n)$$

    divide x by 10 each time, so its time complexity depends on number of digits in x

    • Space complexity : $$O(1)$$

    negative, reverse_num are $$O(1)$$


    Approach #2 String Manipulation [Accepted]

    Algorithm

    1. convert x to string type s
    2. if negative sigh exists, ignore first element(sign itself)
    3. reverse s using string approach (vary from languages)
      • in Python, use s[::-1]
    4. check whether result r is overflow

    Python

    class Solution(object):
        def reverse(self, x):
            """
            :type x: int
            :rtype: int
            """
            s = str(x)
            if x >= 0:
                r = int(s[::-1])
            elif x < 0:
                r = int(s[1::][::-1]) * - 1
            if r <= pow(2, 31) - 1 and r >= -pow(2, 31):
                return r
            else:
                return 0
    

    Complexity Analysis

    • Time complexity : $$O(n)$$

    reversing string is $$O(n)$$

    • Space complexity : $$O(n)$$

    s, r are $$O(n)$$, because they store nearly whole x


    Approach #3 Palindrome method using Array Accessing [Accepted]

    Intuition

    Palindrome approach only needs to iterate $$n/2$$ times, because we swap 2 digits at one time

    e.g. 12345

    turn 1:

    • 1, 5 swap
    • 52341

    turn 2:

    • 2, 4 swap
    • 54321

    Algorithm

    1. convert x to string type, then to array type
      • if negative sign exists, ignore first element
    2. iterate half array
    3. swap current digit with corresponding digit
    4. convert array back to int
    5. handle overflow and negative sign problem

    Python

    class Solution(object):
        def reverse(self, x):
            """
            :type x: int
            :rtype: int
            """
            array = list(str(x)) if x >= 0 else list(str(x))[1:]
            for i in range(int(len(array)/2)):
                array[i], array[len(array) - i - 1] = array[len(array) - i - 1], array[i]
            result = int(''.join(array))
            if result <= pow(2, 31) - 1 and result >= -pow(2, 31):
                return result if x >= 0 else -result
            else:
                return 0
    

    Complexity Analysis

    Time complexity : $$O(n)$$

    • converting is $$O(n+n)$$
      • str(int) is $$O(n)$$
      • list(str) is $$O(n)$$
    • for loop is $$O(n/2)$$

    Space complexity : $$O(n)$$

    array needs $$O(n)$$ for storing each digit in x


Log in to reply
 

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