Solution by iAmADolphin


  • 1
    I

    QUESTION:

    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 hold integers within the 32-bit signed integer range. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

    SOLUTION [Accepted]:

    The tricky part of this problem is that our answer cannot be larger than a 32 bit signed integer.
    Thus, the number we return needs to be in the range from −2,147,483,648 to 2,147,483,647.

    We can reverse the number pretty easily with a while loop and some simple calculations.

    long reversed = 0;
    while(x != 0) {
                int revDigit = x % 10; //mod 10 will give you the 1's place
                reversed *= 10;
                reversed += revDigit; //put the number we just got on the end
                x /= 10; //divide the original int by 10 to drop the 1's place
            }
    if(reversed <= Integer.MAX_VALUE && reversed >= Integer.MIN_VALUE) return (int)reversed;
    else return 0;
    

    Lets take this line by line.

    The variable reversed is of type long because in java that type holds signed 32 bit integers.
    (Exactly what we want!)
    This will be the variable that stores the number as we work on it and will be what we return later on.

    The while loop will keep going while x is not 0.

    We declare revDigit and assign it the value x % 10 .
    This modulo operation will return whatever the remainder is if you divided x / 10.
    Meaning 132 % 10 == 2.
    Now revDigit has the value in the 1's place.

    We Multiply reversed by 10 to clear up the 1's place for the next number coming in from x.
    (ex. if reversed were 13, after this it would be 130.)

    We now add revDigit that we calculated earlier to reversed.

    Finally, we assign x the value of itself divided by 10.
    (ex. if x were 132, then after x would be 13.)

    This loop continues until x is 0.
    (ex. At the end of the loop if x were 3 then x /= 10 would be 0.)

    Now, reversed holds the digits that were in x in reversed order. However, this number could be larger than what a 32 bit signed integer can hold.

    For example, 1,000,000,009 is a perfectly valid integer. However, if it were reversed it would be 9,000,000,001 which is greater than the maximum value of a 32 bit signed integer (2,147,483,647).

    Thus we must check to make sure that reversed is within the range of signed integers that can be represented with 32 bits.

    if(reversed <= Integer.MAX_VALUE && reversed >= Integer.MIN_VALUE) return (int)reversed;
    else return 0;
    

    This checks to make sure reverse is within the valid integer range and if not, returns 0.

    reverse is first cast back into an int because the method is declared with int as the return type.

    Complexity Analysis

    For a given integer n, the loop will run a total of log10(n) times. Thus the time complexity is log(n).


Log in to reply
 

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