☕ DSA Java Articles

Topics › Basics › Know Basic Maths

Reverse a number

Easy TUF ID 376 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given a 32-bit signed integer n. Return the integer formed by writing the decimal digits of n in reverse order. The sign stays where it is: -123 becomes -321. Trailing zeros of the input become leading zeros of the output and therefore vanish: 120 becomes 21.

The LeetCode version (“Reverse Integer”) adds one rule: if the reversed value does not fit in a 32-bit signed integer, return 0, and you may not use 64-bit arithmetic to detect that. The TUF version only asks for the reversal. The code below handles both, and the optimal approach obeys the no-64-bit rule.

Constraints: -2^31 ≤ n ≤ 2^31 - 1.

Example 1

n = 123
answer = 321

Example 2

n = -120
answer = -21        // sign kept, trailing zero dropped

Example 3

n = 1534236469
answer = 0          // reversed it would be 9646324351, which exceeds 2^31 - 1

Approach 1: Brute force, via a string

Intuition. Reversing a sequence of characters is a solved problem: StringBuilder.reverse(). So write the absolute value as a string, reverse it, parse it back into a long, reapply the sign and check the range. Long.parseLong happily ignores leading zeros, so "021" parses as 21.

Algorithm.

  1. Let abs = |n| as a long (the long matters for Integer.MIN_VALUE).
  2. Convert to a string, reverse, parse as long.
  3. Negate if n was negative.
  4. If the result is outside [Integer.MIN_VALUE, Integer.MAX_VALUE], return 0; otherwise cast to int.
static int bruteForce(int n) {
    long abs = Math.abs((long) n);
    String reversed = new StringBuilder(Long.toString(abs)).reverse().toString();
    long result = Long.parseLong(reversed);
    if (n < 0) result = -result;
    if (result < Integer.MIN_VALUE || result > Integer.MAX_VALUE) return 0;
    return (int) result;
}

Complexity. Time O(d) for d digits. Space O(d) for the string and the builder.

Correct, but it dodges the arithmetic the problem is testing, and it would be disqualified by the LeetCode rule against 64-bit integers.

Approach 2: Better, digit by digit into a long

Intuition. n % 10 is the last digit and n / 10 is the number without it. If we read the digits last-to-first and keep appending each one to an accumulator with rev = rev * 10 + digit, the accumulator receives the digits in reverse order, which is exactly the reversed number. Trailing zeros of n are appended first, when rev is still 0, so 0 * 10 + 0 keeps rev at 0 and they disappear naturally.

We work on the absolute value in a long, so the reversal of any 10-digit input (at most 9,999,999,999) fits without overflow, and we compare with the int limits at the end.

Algorithm.

  1. x = |n| as a long, rev = 0.
  2. While x > 0: rev = rev * 10 + x % 10, then x /= 10.
  3. Negate rev if n < 0.
  4. Return 0 if rev is outside the int range, else (int) rev.
static int better(int n) {
    long x = Math.abs((long) n);
    long rev = 0;
    while (x > 0) {
        rev = rev * 10 + x % 10;
        x /= 10;
    }
    if (n < 0) rev = -rev;
    if (rev < Integer.MIN_VALUE || rev > Integer.MAX_VALUE) return 0;
    return (int) rev;
}

Dry run on n = 123:

x x % 10 rev after step
123 3 3
12 2 32
1 1 321
0   loop ends, return 321

Complexity. Time O(d). Space O(1).

This is the version to write when 64-bit integers are allowed; it is short and every line is obviously right.

Approach 3: Optimal, int only with an overflow guard

Intuition. Without a long, we must detect overflow before it happens. The step that can overflow is rev * 10 + digit. It is safe exactly when the new value stays in range, i.e. rev * 10 + digit ≤ 2147483647. Rearranged into checks that never overflow themselves:

The mirror image holds for the negative side with Integer.MIN_VALUE / 10 = -214748364 and the digit bound -8.

A second trick removes all sign handling: in Java, % keeps the sign of the dividend and / truncates toward zero, so for negative n every digit is negative and rev is built as a negative number directly.

Algorithm.

  1. rev = 0.
  2. While n != 0: digit = n % 10, n /= 10.
  3. If appending digit would exceed Integer.MAX_VALUE or go below Integer.MIN_VALUE (the two checks above), return 0.
  4. rev = rev * 10 + digit.
  5. Return rev.
static int optimal(int n) {
    int rev = 0;
    while (n != 0) {
        int digit = n % 10;                      // negative when n is negative, so the sign takes care of itself
        n /= 10;
        if (rev > Integer.MAX_VALUE / 10 || (rev == Integer.MAX_VALUE / 10 && digit > 7)) return 0;
        if (rev < Integer.MIN_VALUE / 10 || (rev == Integer.MIN_VALUE / 10 && digit < -8)) return 0;
        rev = rev * 10 + digit;
    }
    return rev;
}

Complexity. Time O(d), at most ten iterations for an int. Space O(1).

Why is the digit > 7 check actually redundant for valid inputs? If rev == 214748364 we have already consumed nine digits, so the input had ten digits and started with a 1 or 2 (anything larger exceeds 2^31 - 1), making the last digit appended at most 2. The check costs nothing and keeps the method correct for any caller, so leave it in.

Edge cases and pitfalls