Reverse Integer — The Upside-Down Meter

Boss 7: The Upside-Down Meter

The dungeon finale, and it plays a trick on you: there's not a single << or ^ in sight. Six bosses lived in base 2. The seventh hands you base 10 and asks whether you actually learned the lesson or just memorized the operators.

Because the lesson was never "XOR is neat". The lesson was that a number lives in a register of fixed width, and everything you do to it has to respect that width. Boss 4 peeled bits off one end and pushed them onto the other. Boss 6 masked every sum back into 32 bits because the register demanded it. This boss runs the exact same peel-and-push loop on decimal digits, and the entire fight is the moment before the push: will this one overflow the register?

The story

The utility company's newest installer had one job. The meter went onto the wall upside down.

Nobody noticed for months. The automated logger photographed the dial every night and dutifully recorded what it saw, which was every reading with its digits reversed. A house that used 123 units is on the books for 321. A big apartment block that ran up 9646324351... well, that one's interesting, hold the thought.

You're the tech sent to fix the ledger. For each logged number, reverse the digits back. Negative adjustment entries exist too (refunds, corrections), and the minus sign was hand-stamped by the clerk, so it's already the right way up: -321 un-reverses to -123.

One hard rule. The billing system's register is a signed 32-bit slot: it holds nothing above 2147483647 and nothing below -2147483648. If an un-reversed reading won't fit, the system must not try to store it, not even for an instant during the arithmetic. Flag it as invalid, log a zero, move on. A corrupted register is worse than a missing reading.

The problem, dressed up properly

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit range [-2**31, 2**31 - 1], return 0. Assume the environment does not allow you to store 64-bit integers.

LeetCode 7, "Reverse Integer". Medium-rated, ancient, and famously not about the reversing. It's about that last sentence.

The naive attempt

Python makes the reverse itself a one-liner. Flip the string, juggle the sign, range-check at the end:

def reverse(x: int) -> int:
    sign = -1 if x < 0 else 1
    rev = sign * int(str(abs(x))[::-1])
    if rev < -2**31 or rev > 2**31 - 1:
        return 0
    return rev

This passes LeetCode. It is also cheating, and it's worth being precise about why.

The check happens after rev already holds the oversized value. That's fine in Python, where integers grow without limit and 9646324351 sits in memory as comfortably as 7. But the problem statement built you a smaller world on purpose: an environment where nothing wider than 32 bits can be stored. In that world, the oversized value never exists to be checked. The multiply overflows first, the register now holds garbage (or, in C, you've hit undefined behavior), and your careful comparison inspects the garbage and nods it through.

Build-it-then-check-it is not an option when building it is the crash. The whole exercise is learning to check a boundary you're not allowed to touch.

The weapon: pop, guard, push

The reverse itself is the loop this dungeon has drilled twice already. Pop the last digit off x, push it onto rev:

digit = x % 10      # pop the low digit
x //= 10            # drop it
rev = rev * 10 + digit   # push it onto the other number

Boss 4 did exactly this with n & 1 and shifts, one bit at a time. Base 10 just changes the divisor. The new material is the guard, so let's derive it instead of pasting it.

Call the limit M = 2147483647. The dangerous step is rev * 10 + digit. We need to know, using only values that fit, whether that expression would exceed M. Divide the limit instead of multiplying the value: M // 10 is 214748364, and that division is always safe because it makes numbers smaller. Now compare:

• If rev is strictly greater than 214748364, then rev * 10 alone is at least 2147483650. Overflow, no matter the digit.
• If rev equals 214748364 exactly, then rev * 10 is 2147483640, and the push survives only if digit is at most 7, because M ends in 7.
• If rev is below 214748364, then rev * 10 + digit is at most 2147483639 plus 9. Safe.

So the guard, checked before the push, is: overflow when rev > 214748364, or when rev == 214748364 and digit > 7. Every quantity in that test already fits in 32 bits. We interrogate the boundary without ever stepping over it.

One Python-specific landmine before the code. Python's % follows the sign of the divisor, so -123 % 10 is 7, not -3, and -123 // 10 is -13, not -12. Run the pop loop on a negative number directly and it pops nonsense digits forever. The clean fix is the one the story already suggested: the minus sign was stamped separately, so peel it off, reverse the absolute value, stamp it back at the end.

def reverse(x: int) -> int:
    INT_MAX = 2**31 - 1        # 2147483647
    sign = -1 if x < 0 else 1
    x = abs(x)                 # Python quirk: -123 % 10 is 7, so shed the sign first
    rev = 0
    while x:
        digit = x % 10         # pop
        x //= 10
        # guard BEFORE the push: would rev * 10 + digit leave the register?
        if rev > INT_MAX // 10 or (rev == INT_MAX // 10 and digit > 7):
            return 0
        rev = rev * 10 + digit # push, now provably safe
    return sign * rev

O(log₁₀ x) iterations, one per digit, constant space. And yes, Python would have let us skip the guard entirely. That's exactly why the problem forbids it: the guard is the boss.

Watching it work

The easy house first, x = 123:

digit  x     rev    guard
3      12    3      0 is far below 214748364, push
2      1     32     3 is far below, push
1      0     321    32 is far below, push
end: +321 ✓

Now the apartment block, x = 1534236469, a perfectly legal 32-bit reading whose mirror image is not:

digit  x           rev         guard
9      153423646   9
6      15342364    96
4      1534236     964
6      153423      9646
3      15342       96463
2      1534        964632
4      153         9646324
3      15          96463243
5      1           964632435
1      0           —           964632435 > 214748364 → return 0 ✗

Nine digits push through clean. On the tenth, rev is 964632435, already far beyond 214748364, so multiplying by ten would land around 9.6 billion, more than four registers wide. The guard fires before the multiply, the reading gets flagged, and the billing register never sees a corrupt value. The full reverse would have been 9646324351, and no 32-bit slot on earth can hold it.

Gotchas

1. Python's negative modulo will gaslight you. -123 % 10 is 7 and -123 // 10 is -13, because Python rounds floor-ward and keeps the remainder's sign matching the divisor. C and Java truncate toward zero and would give you -3 and -12. Port a C solution line-for-line into Python and the pop loop breaks on the very first negative input. Handle the sign explicitly: work on abs(x), multiply the sign back at the end.

2. Guarding after the push. rev = rev * 10 + digit followed by if rev > INT_MAX: return 0 looks equivalent and passes in Python. In the 32-bit world the problem defines, it's the naive attempt wearing a trench coat: the overflow has already corrupted the register (or triggered undefined behavior in C) by the time the check runs. The guard must compare rev against INT_MAX // 10 before the multiply exists.

3. The range isn't symmetric, and it mostly doesn't matter here. Signed 32-bit runs from -2147483648 to 2147483647; the negative side reaches one further. Working on the absolute value and checking against INT_MAX looks like it might wrongly reject a legal -2147483648-flavored result. It can't: for a reversed absolute value to equal 2147483648, the original input would have to be 8463847412 with a sign, which is ten digits past anything a 32-bit input can be. The asymmetry is real and worth knowing (Boss 6's mask forced us through it), it just never bites on valid input here. Bonus trivia: rev == INT_MAX // 10 with digit > 7 is likewise unreachable for legal inputs, since a ten-digit 32-bit number must start with 1 or 2, but you write the full guard anyway, because the guard documents the boundary, not just the reachable part of it.

4. Trailing zeros vanish, and that's correct. Reverse 120 and you get 21, not 021 or 210. Integers have no leading zeros, so the pop-and-push loop drops them naturally: the zero pops first, pushes as rev = 0 * 10 + 0, and contributes nothing. In meter terms, a reading of 021 was always just 21. No padding logic needed, and adding any is a bug.

Complexity

One loop iteration per decimal digit, a handful of integers total.

Time: O(log₁₀ x), the digit count. Space: O(1).

A 32-bit integer has at most ten digits, so in practice this is "at most ten laps", which is as close to free as algorithms get.

Boss down. Dungeon cleared.

The corrected ledger posts, the installer is sent back with a spirit level, and Dungeon 17 goes dark. Seven bosses, and the bit toolkit is complete:

• XOR cancel (Boss 1, The Unclaimed Ticket): pairs erase themselves, the survivor remains
• Kernighan clear (Boss 2, The Punch Card Count): n & (n - 1) deletes the lowest set bit, pay per hole, not per column
• Shift-DP (Boss 3, The Locker Stencils): every count steals from the count of n >> 1, a whole table for the price of a shift
• Peel and relocate (Boss 4, The Backwards Banner): pop bits off one end, push onto the other, the loop this finale ran in base 10
• Manufactured twins (Boss 5, The Roll Call Gap): XOR the list against the full roster and the missing number is the one without a partner
• XOR as half-adder (Boss 6, The Broken Plus Key): sum without carry, carry via AND-and-shift, addition rebuilt from logic gates
• Register-width discipline (Boss 7, The Upside-Down Meter): respect the width of the slot you're writing into, and check the boundary from the safe side

The through-line: bits were never tricks. They're what numbers are, and every "trick" in this dungeon was just arithmetic with the abstraction peeled off. XOR is addition that forgot how to carry. Kernighan is subtraction's borrow, cashed in. Overflow is a register running out of wall. Sixteen dungeons built structures on top of numbers; this one showed you the numbers were structures all along.

Next: Dungeon 18, Math & Geometry. The last dungeon of the quest. Matrices rotating in place, spirals unwinding, happy numbers chasing their own tails, and pow(x, n) computed in logarithmic strides. Eighteen dungeons, one final gate, and everything you've carried since Dungeon 1 comes along for the ending. See you there.