Reverse Integer

Medium Arrays & Hashing Math / Number Theory Original on LeetCode

Reverse Integer is a medium arrays & hashing problem solved with the math / number theory pattern. The best approach, optimal (pop digits with overflow guard), runs in O(d) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (string reversal) up.

Problem

You are given a signed 32-bit integer x. Return the number you get by writing the digits of x in reverse order, keeping its sign.

If the reversed value falls outside the signed 32-bit range [-2^31, 2^31 - 1], return 0 instead. Assume the environment cannot store 64-bit integers, so the overflow has to be detected before it happens.

Examples

Example 1

Input
x = 4073
Output
3704
Why
The digits 4, 0, 7, 3 read backwards give 3704.

Example 2

Input
x = -560
Output
-65
Why
The sign stays in front and the trailing zero becomes a leading zero, which disappears.

Example 3

Input
x = 1999999999
Output
0
Why
Reversed it would be 9999999991, which does not fit in a signed 32-bit integer, so the answer is 0.

Constraints

  • -2^31 <= x <= 2^31 - 1
  • You may only use 32-bit integer arithmetic in the optimal approach (no 64-bit values).

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (string reversal)O(d)O(d)
Optimal (pop digits with overflow guard)O(d)O(1)

1Brute force (string reversal)

TimeO(d)d is the number of digits (at most 10); each one is copied and reversed once.
SpaceO(d)The string holds the d digits.

Turn the absolute value into a string, reverse it, parse it as a 64-bit number, put the sign back and check whether it still fits in 32 bits. Simple, but it relies on a wider integer type.

  1. Take the absolute value of x as a 64-bit number and convert it to a string.
  2. Reverse the string and parse it back into a 64-bit number.
  3. Apply the original sign.
  4. If the value is outside [-2^31, 2^31 - 1], return 0; otherwise return it.
class Solution {
    public int reverse(int x) {
        long abs = Math.abs((long) x);
        String rev = new StringBuilder(Long.toString(abs)).reverse().toString();
        long value = Long.parseLong(rev);
        if (x < 0) value = -value;
        if (value < Integer.MIN_VALUE || value > Integer.MAX_VALUE) return 0;
        return (int) value;
    }
}

2Optimal (pop digits with overflow guard)

TimeO(d)One loop iteration per digit, and an int has at most 10 digits.
SpaceO(1)Only a few integer variables.

Peel off the last digit with % 10 and push it onto the result with result * 10 + digit. Before every push, check whether the multiplication would cross the 32-bit limits; if it would, the answer is 0. In Java the remainder keeps the sign of x, so negative numbers work without special handling.

  1. Set result = 0.
  2. While x != 0: digit = x % 10, x = x / 10.
  3. If result > MAX / 10, or result == MAX / 10 and digit > 7, return 0.
  4. If result < MIN / 10, or result == MIN / 10 and digit < -8, return 0.
  5. result = result * 10 + digit.
  6. Return result.
class Solution {
    public int reverse(int x) {
        int result = 0;
        while (x != 0) {
            int digit = x % 10;
            x /= 10;
            if (result > Integer.MAX_VALUE / 10 || (result == Integer.MAX_VALUE / 10 && digit > 7)) return 0;
            if (result < Integer.MIN_VALUE / 10 || (result == Integer.MIN_VALUE / 10 && digit < -8)) return 0;
            result = result * 10 + digit;
        }
        return result;
    }
}

Edge cases to test

  • x = 0
  • Trailing zeros, like 1200, which reverse to 21
  • Negative numbers keep their sign
  • Results that overflow just above 2^31 - 1 or just below -2^31
  • x = -2^31 itself (its absolute value does not fit in an int)

Hints

Hint 1

x % 10 gives the last digit and x / 10 drops it. Build the answer one digit at a time.

Hint 2

Before doing result * 10 + digit, check whether that step would leave the 32-bit range.

Hint 3

Compare result against Integer.MAX_VALUE / 10 and Integer.MIN_VALUE / 10 to detect overflow before it happens.

FAQ

What is the best time complexity for Reverse Integer?

Optimal (pop digits with overflow guard) runs in O(d) time and O(1) extra space. One loop iteration per digit, and an int has at most 10 digits.

Which pattern does Reverse Integer use?

It is a arrays & hashing problem that uses the math / number theory pattern. Other problems with the same pattern: Bulb Switcher, Reaching Points, Water and Jug Problem.

Is there a brute force solution for Reverse Integer?

Yes. Brute force (string reversal) takes O(d) time and O(d) space. Turn the absolute value into a string, reverse it, parse it as a 64-bit number, put the sign back and check whether it still fits in 32 bits.

Which edge cases should I test for Reverse Integer?

x = 0; Trailing zeros, like 1200, which reverse to 21; Negative numbers keep their sign; Results that overflow just above 2^31 - 1 or just below -2^31; x = -2^31 itself (its absolute value does not fit in an int).