Solution by Liav3000


  • 0
    L

    Reversing an integer

    Intuition

    This is a fairly simple problem, but there are still a few places you can make mistakes.

    The core task is to reverse the number. Some languages, such as Python and Ruby have builtin functions or methods that can reverse strings. In other languages you could use a loop, decrementing from the last position in the number, to the first, and inserting those digits into a new number.

    This decremented loop seems more like a string operation than an operation on numbers. And Python's reversed only operates on iterables, and numbers aren't iterable, but strings are?

    Seems like we might benefit from treating the number as a string, for part of this problem.

    Algorithm

    • Let is_negative = True if x is a negative number, and make x positive.
    • Reverse x as if it was a string. This can either be done with a reversed builtin or method in some languages, or with a loop, as in the following psudocode:
    buffer = char[x.length]
    for (i = x.length, i--, i >= 0) {
          buffer[x.length - i] = x[i]
    }
    x_rev = ''.join(buffer) 
    
    • Cast x_rev back to being an int
    • if is_negative is True, set x_rev to be negative
    • if x_rev is within the range of a signed 32bit int, return it. Otherwise, return 0.

    Python3

        def reverse(self, x):
            pos_limit = 2**31
            neg_limit = -2**31 + 1
            is_neg = x < 0
            x = abs(x)
            out = int(''.join(reversed(str(x))))
            if is_neg:
                out *= -1
            if neg_limit <= out <= pos_limit:
                return out
            else:
                return 0
    

    Complexity Analysis

    • Time complexity: we have to look at every digit in the integer, which is O(n), where n is the length of x as a string. We need to allocate a new string of the same length, which is also O(n). All our other logic is O(1). Time complexity is O(n)
    • Space complexity is O(n) for the same reason above: the new string allocated is the same length as the input.

Log in to reply
 

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