Reverse Integer

NeetCode: Reverse Integer · LeetCode: 7. Reverse Integer · Difficulty: Medium

Given a signed 32-bit integer x, return x with its digits reversed. If the reversed value does not fit in a signed 32-bit integer, return 0.

Example

Text

Input:  x = 123           Output: 321
Input:  x = -123          Output: -321
Input:  x = 120           Output: 21
Input:  x = 1534236469    Output: 0     (9646324351 does not fit in a 32-bit int)

Brute force: string and a wider integer

Take the absolute value as text, reverse it, parse it into a long, reapply the sign and check that the result fits in int. Widen x to long before Math.abs: Math.abs(Integer.MIN_VALUE) returns Integer.MIN_VALUE (still negative) because 2^31 does not fit in an int. Up to 10 digits always fit in a long, so the parse cannot overflow.

Java

public class Main {
    static class Solution {
        public int reverse(int x) {
            String digits = new StringBuilder(Long.toString(Math.abs((long) x))).reverse().toString();
            long value = Long.parseLong(digits);
            if (x < 0) {
                value = -value;
            }
            if (value < Integer.MIN_VALUE || value > Integer.MAX_VALUE) {
                return 0;
            }
            return (int) value;
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.reverse(123));
        System.out.println(s.reverse(-123));
        System.out.println(s.reverse(120));
        System.out.println(s.reverse(1534236469));
        System.out.println(s.reverse(Integer.MIN_VALUE));
        System.out.println(s.reverse(0));
    }
}

Output

Time: O(d) for d digits (at most 10). Space: O(d) for the string.

Optimal: pop and push digits with checked arithmetic

Peel the last digit off x with x % 10 and x / 10, and push it onto the result with rev * 10 + digit. In Java, / truncates toward zero and % keeps the sign of the dividend, so a negative x produces negative digits and the sign takes care of itself; Integer.MIN_VALUE needs no special case either. The only danger is the push overflowing int, and int arithmetic wraps silently. Math.multiplyExact and Math.addExact throw ArithmeticException on overflow instead, so catching it gives the answer 0. No wider type and no string is needed.

Java

public class Main {
    static class Solution {
        public int reverse(int x) {
            int rev = 0;
            while (x != 0) {
                int digit = x % 10;
                x /= 10;
                try {
                    rev = Math.addExact(Math.multiplyExact(rev, 10), digit);
                } catch (ArithmeticException overflow) {
                    return 0;
                }
            }
            return rev;
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.reverse(123));
        System.out.println(s.reverse(-123));
        System.out.println(s.reverse(120));
        System.out.println(s.reverse(1534236469));
        System.out.println(s.reverse(Integer.MIN_VALUE));
        System.out.println(s.reverse(0));
        System.out.println(s.reverse(-2147447412));
    }
}

Output

321
-321
21
0
0
0
-2147447412

Time: O(d), at most 10 iterations. Space: O(1).