Palindrome Number

Given an integer, return true if it is a palindrome (reads the same forward and backward). Converting to string is easy but not required; the numeric approach avoids extra space.

Why this is worth learning

Reverse only the suffix until it meets the remaining prefix. This compares decimal structure without constructing the entire reversed integer, whose value might overflow.

Before coding: one-minute experiment

For 12321, what are x and rev when the loop first stops, and which final comparison accepts it?

Function signature

func IsPalindrome(x int) bool

Inputs / outputs

• x: integer.
• Return: true if palindrome, else false.

Example

121 -> true
-121 -> false (negative sign)
10 -> false (leading zero would be needed)

Constraints

• Fits in 32-bit signed integer.

Core idea (near-solution)

Converting to a decimal string and comparing mirrored positions is a valid O(d)-time baseline for d digits. To use constant extra space, divide off the low digits while rebuilding them in reverse. A full reversal is unnecessary and can overflow; once the rebuilt suffix meets the remaining prefix, compare halves. A middle digit is allowed to remain unmatched, but a positive trailing zero needs an early rejection.

Reverse only half the number and compare. This avoids overflow and extra work.

Invariant: after each step, rev is the reverse of the processed suffix of x.

Algorithm (step-by-step)

1. If x < 0, return false. If x % 10 == 0 and x != 0, return false.
2. Build rev by extracting digits until rev >= x.
3. The number is a palindrome if x == rev (even length) or x == rev/10 (odd length).

Correctness sketch

After k iterations, rev is the reverse of the k removed low decimal digits and x is the unconsumed high prefix. Removing one digit with modulo/division and appending it to rev preserves that relation. Negative values cannot match a leading minus sign, and a positive trailing zero cannot match a nonzero leading digit, so reject them first. When x<=rev, roughly half the digits have been consumed. Even-length palindromes have x==rev; odd-length palindromes have x==rev/10 because the middle digit is irrelevant. Other inputs fail both comparisons. Within the signed-32-bit domain, reversing only half avoids full-reversal overflow.

Trace (hand walkthrough)

Example input:
121 -> true
-121 -> false (negative sign)
10 -> false (leading zero would be needed)

Walk:
- x=121: rev=1, x=12; rev=12, x=1 -> x==rev/10 -> true
- x=-121 -> negative -> false; x=10 ends with 0 -> false

Pitfalls to avoid

• Reversing the full number (can overflow).
• Treating negative numbers as palindromes.
• Forgetting the trailing zero rule.

Debugging lens

Test zero, negative values, positive multiples of ten, and odd/even digit counts. Removing the trailing-zero guard can incorrectly accept cases such as 10.

Complexity

• Time: O(log10 x).
• Extra space: O(1).

Implementation notes (Go)

• Integer division and modulo are safe for non-negative numbers.

Reconstruction checkpoint

For 12321, what are x and rev when the loop first stops, and which final comparison accepts it?

Return to Math · Module quiz