LeetCode 7 · Bit Manipulation

Reverse Integer, explained with a picture

Spinning an odometer backwards, watching for overflow.

MediumBit Manipulation
▶ Watch it step by step

The problem

Reverse the digits of a 32-bit signed integer. If the result would overflow the 32-bit range, return 0.

Input:  −123
Output: −321

Picture it

Picture an odometer spinning backwards. Remember the sign, then repeatedly take the last digit (x mod 10), drop it from x, and append it to the result (result × 10 + digit). Before each append we check whether the result would go past the 32-bit limit; if so, the answer is 0.

How to recognise it

  • You must rearrange the decimal digits of a number: reverse them.
  • x % 10 reads the last digit and x // 10 removes it, so digits can be taken off one at a time without strings.
  • Building the answer with out * 10 + digit appends a digit on the right, which reverses the order.
  • The twist is the 32-bit limit: if the reversed number is outside −2^31 to 2^31 − 1, return 0. The input itself is always inside that range.

Start with brute force

Turn the number into text, reverse the text, and turn it back, keeping the sign apart.

def reverse_brute(x):
    sign = -1 if x < 0 else 1
    out = sign * int(str(abs(x))[::-1])
    return out if -2**31 <= out < 2**31 else 0

It is correct and O(d) for d digits (at most 10), so it is not slow. Leading zeros vanish on their own: "021" reads back as 21. Interviewers usually want the arithmetic version, and the problem adds a rule (below) that the string approach also ignores.

From brute force to the idea

  1. Find the waste. The string detour converts every digit to a character and back; arithmetic can move digits directly.
  2. Handle the sign once. Python's % and // round towards minus infinity, so -123 % 10 is 7, not 3. The shown code saves the sign and works on abs(x), where both behave as expected.
  3. Move digits across. Each round takes the last digit (x % 10), appends it to out (out * 10 + digit), and removes it from x (x //= 10). When x reaches 0 every digit has moved.
  4. Check the range. Restore the sign, then return 0 if the result is outside −2^31 to 2^31 − 1.

This is the key idea: pop the last digit with % 10 and push it with * 10 +, then check the 32-bit range.

The problem statement says to assume the machine cannot store 64-bit integers. The shown code does not follow that rule: it builds the full reversed value (up to 10 digits, such as 9,646,324,351) and only then compares, which is fine in Python because integers have no size limit. In Java or C++, check before each step instead: if out > (2^31 − 1) // 10, the next out * 10 would overflow, so return 0.

The key idea

Pop and push digits with % and //, checking against 2³¹ − 1 before each push.

Python solution

def reverse(x):
    sign = -1 if x < 0 else 1
    x, out = abs(x), 0
    while x:
        out = out * 10 + x % 10       # move the last digit over
        x //= 10
    out *= sign
    return out if -2**31 <= out < 2**31 else 0

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute force (string reverse)O(d): build, reverse and parse d characters, d ≤ 10O(d): the string
Digit loop (shown code)O(d): one round per digitO(1): two integers

Edge cases

  • Trailing zeros (120): returns 21.
  • Zero: the loop never runs; returns 0.
  • Negative (-123): returns −321.
  • Overflow (1534236469): the reverse 9,646,324,351 is too big, so it returns 0.
  • Smallest integer (-2147483648): the reverse −8,463,847,412 is too small; returns 0.
  • Just inside the range (1463847412): returns 2,147,483,641, which fits.

Common mistakes

  • Using % and // directly on a negative number in Python: -123 // 10 is −13, and -1 // 10 is −1, so while x: never ends.
  • Checking the range against the input instead of the reversed result.
  • In fixed-width languages, multiplying first and checking afterwards, when the overflow has already happened.
  • Converting through a string and forgetting the minus sign, so int("321-") raises ValueError.
Your turn: palindrome number

Decide whether an integer reads the same forwards and backwards (LeetCode 9), without converting it to a string. 121 is a palindrome, −121 and 10 are not. Describe your approach, then write it if you like.

Compare with our answer

Reverse only the second half of the digits and compare it with the first half; this never builds a number larger than the input. Negative numbers and numbers ending in 0 (other than 0 itself) cannot be palindromes.

def is_palindrome(x):
    if x < 0 or (x % 10 == 0 and x != 0):
        return False
    half = 0
    while x > half:
        half = half * 10 + x % 10
        x //= 10
    return x == half or x == half // 10   # odd length: drop the middle digit

Time O(d), space O(1).

A strong answer mentions: reusing the pop-and-push digit loop, stopping at the middle, the odd-length case, and why trailing zeros rule a number out.

Check what stuck

1. You must check whether the digits of an integer appear in non-decreasing order from left to right, without strings. Which approach fits best?

2. Why does the shown code work on abs(x) instead of x?

3. A learner removes sign and abs and loops on x directly. What happens for x = −123?

Score 60% or more and the lesson is marked complete.