LeetCode 7 · Medium · Bit Manipulation

Reverse Integer

Reverse the decimal digits of a signed 32-bit integer x, keeping its sign. If the reversed value falls outside [−2³¹, 2³¹ − 1], return 0. Assume you cannot store 64-bit integers.

O(log x)time · one round per digit
O(1)space
check firstthen res·10 + digit

a whole number from −2147483648 to 2147483647

digits pop the last digit of rest, push it onto the end of res · bound = (limit − digit) / 10, the largest safe res

digit
public int reverse(int x) { long limit = x >= 0 ? Integer.MAX_VALUE : 1L << 31; // max |answer| long rest = Math.abs((long) x); long res = 0; while (rest != 0) { long digit = rest % 10; // pop the last digit rest /= 10; if (res > (limit - digit) / 10) { // res*10+digit > limit return 0; } res = res * 10 + digit; // push it } return (int) (x >= 0 ? res : -res);}
rest
—
digit
—
bound
—
res
0

Why it works

  1. Brute force through a string: reverse the digits of Math.abs((long) x) as a string, parse them with Long.parseLong, re-apply the sign and compare with the limits. Simple, but the parsed value can exceed 32 bits before you check it, which the problem forbids.
  2. Pop and push digits: rest % 10 is the last digit and rest / 10 drops it; res * 10 + digit appends it. After every round, res holds the popped digits in reverse order.
  3. Check before you multiply. res * 10 + digit > limit is the same as res > (limit − digit) / 10, which uses only numbers that fit in 32 bits. One round per digit: O(log₁₀ x) time, O(1) space.
  4. Pitfall: the two limits differ. 2³¹ − 1 = 2147483647 but −2³¹ = −2147483648, so a negative answer may be one larger in magnitude. Working with the absolute value and a sign-dependent limit keeps that straight. Use long for rest, res and limit: Math.abs(Integer.MIN_VALUE) is still negative, and 2³¹ does not fit in an int.
  5. Pitfall: trailing zeros just vanish (120 → 21), because pushing a 0 onto an empty res keeps it 0. Related: Palindrome Number (9) reverses half the digits the same way.