Skip to main content

Reverse Integer

Reverse Integer: Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-2^31, 2^31 - 1], then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

Example 1:​
Input: x = 123
Output: 321
Example 2:​
Input: x = -123
Output: -321
Example 3:​
Input: x = 120
Output: 21
Constraints:​
  • -2^31 <= x <= 2^31 - 1

Try this Problem on your own or check similar problems:

  1. Reverse Bits
  2. A Number After a Double Reversal
  3. String to Integer (atoi)
Solution:​
public int reverse(int x) {
    if(x == 0 || x == Integer.MIN_VALUE) return 0;
    boolean isNegative = false;
    if(x < 0){
        x = -x;
        isNegative =  true;
    }

    while(x % 10 == 0) x /= 10;

    int num = 0;
    while(x != 0){
        int rem = x % 10;
        x /= 10;
        if (num > Integer.MAX_VALUE/10 || (num == Integer.MAX_VALUE / 10 && rem > 7)) return 0;
        num = num * 10 + rem;
    }

    return isNegative ? -num : num;
}

Time/Space Complexity:​
  • Time Complexity: O(logx)
  • Space Complexity: O(1)
Explanation:​

The time complexity is constant and it's proportional to the number of digits of input number which is in boundary -2^31 <= x <= 2^31 - 1 which means the number of digits is limited (we put logx since that's how we determine the number of digits). The solution is combination of String to Integer (atoi) for checking integer overflow and Palindrome Number from which we utilize the logic of extracting the last and first digit which we then use with combination of leftPower (bulding the first half of the number) and rightPower (building the second half of the number) to build the number. We also remove any trailing zeroes since 00035 is just 35 for example. Also, since we move in pairs is possible that we will be left with a number which doesn't have a pair (123, we take 1 and 3, but 2 is left after the loop) so we have to place it in the number by multiplying with the current leftPower. Finally, we check if we have a negative number since we recorded it at the beginning of the solution and we return the reversed number as final result.

public int reverse(int x) {
    if(x == 0) return 0;
    boolean isNegative = false;
    if(x < 0){
        x = -x;
        isNegative =  true;
    }

    while(x % 10 == 0) x /= 10;

    int num = 0;
    int numberOfDigits = (int) Math.floor(Math.log10(x));
    int power = (int) Math.pow(10,numberOfDigits);
    int leftPower = power, rightPower = 1;
    while(x > 9){
        int firstDigit = x / power, lastDigit = x % 10;
        x -= firstDigit * power;
        x -= lastDigit;

        if(num + (long) lastDigit * leftPower > Integer.MAX_VALUE) return 0;
        num += lastDigit * leftPower;
        if(num + (long) firstDigit * rightPower > Integer.MAX_VALUE) return 0;
        num += firstDigit * rightPower;

        leftPower /= 10;
        rightPower *= 10;
        x /= 10;
        power /= 100;
    }

    if(x > 0){
        num += leftPower * (x % 10);
    }

    return isNegative ? -num : num;
}

The previous algorithm uses the logic of getting digits in pairs, but there is a simpler version of just taking the last digit and each time moving the current integer by one place (multiply by 10), in this algorithm we also don't use long to check for integer overflow, since by the problem statement we can only use 32-bit integer. To check for integer overflow we first check if num is larger than Integer.MAX_VALUE/10 since then when we multiplied by 10 we will get an overflow. If it's equal to it, then we can only have overflow after we added the rem which ranges 0..9, the maximum integer is 2147483647, so if rem is larger than 7 we will have an overflow.

public int reverse(int x) {
    if(x == 0 || x == Integer.MIN_VALUE) return 0;
    boolean isNegative = false;
    if(x < 0){
        x = -x;
        isNegative =  true;
    }

    while(x % 10 == 0) x /= 10;

    int num = 0;
    while(x != 0){
        int rem = x % 10;
        x /= 10;
        if (num > Integer.MAX_VALUE/10 || (num == Integer.MAX_VALUE / 10 && rem > 7)) return 0;
        num = num * 10 + rem;
    }

    return isNegative ? -num : num;
}