Solution::is_palindrome(1534236469) panics in a debug build.

I copied the function into a scratch crate and called it:

thread 'main' panicked at src/main.rs:31:19:
attempt to multiply with overflow

1534236469 is inside the constraint. The problem allows -2^31 <= x <= 2^31 - 1, and 2^31 - 1 is 2147483647. is_palindrome(2147483647) panics the same way.

Here is the whole function:

pub fn is_palindrome(x: i32) -> bool {
    if x < 0 {
        return false;
    }
    let mut num = x;
    let mut rev = 0;
    while num > 0 {
        rev = rev * 10 + num % 10;
        num /= 10;
    }
    rev == x
}

The reversal never becomes a string

The interesting decision in this file is the one the problem statement never asks for. A palindrome check on a number is easy to solve by turning the number into a string and comparing it to its reverse. That solution builds a String, builds a second one for the reversal, and compares them.

This one never builds either. It peels digits off the input with num % 10 and num /= 10 and folds them into an accumulator, so the reversal happens inside the integer. I counted allocations with a custom global allocator:

shipped is_palindrome(121) = true, allocations during the call: 0
string variant is_palindrome(121) = true, allocations during the call: 2

Zero. The string variant is my code, written to compare. The shipped version does no allocation at all, and it did not have to ask a library to hold the number for it.

One line, and it is the problem

The loop is three lines and one of them is the problem.

rev = rev * 10 + num % 10;

For 1534236469 the digits come off the end in this order: 9, 6, 4, 6, 3, 2, 4, 3, 5, 1. By the time nine of them have accumulated, rev holds 964632435, and rev * 10 wants 9646324350. That is larger than 2147483647, so the multiply overflows, and the panic names the multiply rather than the addition.

The constraint bounds the input. It says nothing about the reversal, and for a ten-digit input the reversal can be a ten-digit number that does not fit in the type the input came in as.

The tests do not see any of this:

assert_eq!(Solution::is_palindrome(121), true);
assert_eq!(Solution::is_palindrome(-121), false);
assert_eq!(Solution::is_palindrome(10), false);

Three digits, one negative, one trailing zero. Every input in the file is short enough that the reversal fits.

Release keeps going

Release builds have overflow checks off, so the multiply wraps and the function keeps going. The wrapped result for 1534236469 is 1056389759, and the function returns false:

is_palindrome(1534236469) = false

That is the correct answer, reached through a number that is not the reversal of anything. Release mode computes the reversed digits modulo 2^32 and compares that to the input.

I did not want to publish a claim like “that is harmless” based on my own reasoning about wrapping arithmetic, so I brute-forced it. Every non-negative in-spec input, all 2,147,483,647 of them, comparing the release build’s answer against the true answer:

checked 2147483648 non-negative in-spec inputs
release-mode disagreements with the true answer: 0

Zero disagreements. The debug build is the one that is honest about what the code is doing, and it does it by crashing on inputs the problem allows.

Reverse half the number and the overflow goes away

The problem’s third hint says to reverse only half the number and compare with the other half. That is the fix, because it makes the overflow unreachable rather than merely detectable: the accumulator only ever holds half the digits, so it never needs more than six of them.

Here is my version:

pub fn is_palindrome(x: i32) -> bool {
    if x < 0 || (x % 10 == 0 && x != 0) {
        return false;
    }
    let mut num = x;
    let mut rev = 0;
    while num > rev {
        rev = rev * 10 + num % 10;
        num /= 10;
    }
    num == rev || num == rev / 10
}

rev never grows past six digits. I checked every ten-digit in-spec input and the largest value the accumulator reached was 214734, which happens for 2147437412, where the first five digits are just barely larger than the last five digits reversed and the loop gets one extra turn. Six digits cannot overflow an i32, so there is no multiply in this version that can fail.

I also ran this version against the true answer, over every ten-digit in-spec input and over a stride-seven sample of the whole non-negative range. Zero disagreements.

The trailing-zero check handles 10 and every other number ending in zero. Without it, the half-reversal of 10 compares 0 with 0 and reports a palindrome; I checked, and it returns true.

The repo has a later solution that keeps the full reversal and guards the overflow instead, which is a different idea and worth its own post: The Overflow Guard Is Not Defensive.

The kind of wrong nobody can see

The shipped code is the better solution. It allocates nothing, it needs no string, and it answers in one pass. Its one mistake is that it assumes the reversal of an i32 is still an i32, and it makes that assumption in the one line that multiplies.

The tests cannot catch it, because the tests are all short. And a release build cannot catch it, because a release build will happily compare a wrapped number against the input and call the result an answer.

I have not changed the file, and I am not sure I will. What I have started doing instead is to ask, before I trust a release build, whether the accumulator in the loop can end up holding more than the input did. That question is cheap, and it is the one that would have caught this.


Next: The Empty Vector Panicked