Solution in C++


  • 0
    C

    Approach #1 use signed int [Accepted]

    
    class Solution
    {
    public:
        int reverse(int x)
        {
            int sign, output;
            (x > 0) ? (sign = 1) : (sign = 0, x = -x);
            for (output = 0; x > 0; x /= 10)
            {
                if (output > 0x7fffffff / 10)
                    return 0;
                output = output * 10 + x % 10;
            }
            return sign ? output : -output;
        }
    };
    
    

    Time complexity: O(n)
    Space complexity: O(1)

    We are going to move the lowest digit of input **x** to the **output** as its new lowest digit, then repeat the action until the numbers of **x** run out. As for the sign of **x**, here is an addition step to mark the sign and transform **x** to its opposite before the iteration.

    Do not compare a **int** with marcro **INT_MAX** or **INT_MIN** directly because once a variable (**temp** for example) saves as **int**, it always satisfies **INT_MIN** <= **temp** && **temp** <= ***INT_MAX** and it is impossible to catch overflow by the comparsion.

    Since the problem require a 32-bit integer input, we illustrate here with 2147483647 = 231 - 1 instead of **INT_MAX**.

    • If we get a intermediate result not larger than 214748363, it is OK whatever the lowest digit of x remianed is, because the operatation output = output * 10 + x % 10; produce a value not more than 2147483639, which is proper for a int.

    • If we get a intermediate result as 214748364, meanwhile the lowest digit of x remianed is 0 or 1 or 2 or ... or 7, it is still OK because the operatation output = output * 10 + x % 10; produce a value not more than 2147483647. Although it seems to fail if the lowest digit of x remianed is 8 or 9, but it is impossible to happen for the input x itself satisfies x <= INT_MAX and the largest value possible is 2147483641 <=> 1463847412. So the condition if (output > 0x7fffffff / 10) is enough.

    Approach #2 use long long [Accepted]

    
    class Solution
    {
    public:
        int reverse(int x)
        {
            int sign;
            long long output;
            (x > 0) ? (sign = 1) : (sign = 0, x = -x);
            for (output = 0; x > 0; x /= 10)
            {
                output = output * 10 + x % 10;
                if (output > 0x7fffffff)
                    return 0;
            }
            return sign ? output : -(signed int)output;
        }
    };
    
    
    Time complexity: O(n) Space complexity: O(1)

    Another way to catch overflow is using a longer datatype such as **long long** and compare it with **INT_MAX**, the idea is easy to come up with but maybe slower then the signed int approach.


Log in to reply
 

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