Solution by awice


  • 0

    Approach #1: Ad-Hoc [Accepted]

    Intuition

    In a typical case like reversing 123, we want to process the digits from right to left, building our answer as we go. We can use $$x % 10$$ to get the last digit, and $$x // 10$$ to truncate the last digit.

    Algorithm

    Process the digits from right to left. For each digit d, we can append it to the right of our current answer by ans = ans * 10 + d.

    To handle negative integers, we'll remember the sign of the integer and correct it at the end.

    To handle integer overflow, we'll check that the integer fits the bounds at the end. In static-typed languages, we can choose eg. long long ans = 0 so that there is enough space in memory to handle a slightly larger number.

    Python

    class Solution(object):
        def reverse(self, x):
            sign = -1 if x < 0 else 1
            x = abs(x)
            ans = 0
            while x > 0:
                ans = 10 * ans + x % 10
                x //= 10
            ans *= sign
    
            return ans if ans.bit_length() < 32 else 0
    

    Complexity Analysis

    • Time Complexity: $$O(N)$$, where $$N$$ is the length of the number. We take $$N$$ steps in our while loop to compute the reversed integer. Alternatively, this would be $$O(\log_{10}{x})$$ where $$x$$ is the given number.

    • Space Complexity: If the integer is guaranteed to fit in 32 or 64 bits, then there is $$O(1)$$ additional space used for the reversed integer. Otherwise, if the integer is arbitrarily big, then $$O(N)$$ additional space is used to store the reversed integer.


Log in to reply
 

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