Overflow in intermediate arithmetic
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
A visual walkthrough of the half-reversal approach — check if a number reads the same backwards, without converting it to a string.
Given an integer x, return true if x is a palindrome, and false otherwise.
Example 1:
Input: x = 121 Output: true Explanation: 121 reads as 121 from left to right and from right to left.
Example 2:
Input: x = -121 Output: false Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.
Example 3:
Input: x = 10 Output: false Explanation: Reads 01 from right to left. Therefore it is not a palindrome.
Constraints:
-231 <= x <= 231 - 1The simplest approach: convert the integer to a string and check if it reads the same forwards and backwards.
// Brute force: convert to string public boolean isPalindrome(int x) { String s = String.valueOf(x); return s.equals(new StringBuilder(s).reverse().toString()); }
// Brute force: convert to string func isPalindrome(x int) bool { s := strconv.Itoa(x) runes := []rune(s) for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 { if runes[i] != runes[j] { return false } } return true }
# Brute force: convert to string def is_palindrome(x: int) -> bool: s = str(x) return s == s[::-1]
// Brute force: convert to string pub fn is_palindrome_str(x: i32) -> bool { let s = x.to_string(); let rev: String = s.chars().rev().collect(); s == rev }
// Brute force: convert to string function isPalindrome(x: number): boolean { const s = String(x); return s === s.split('').reverse().join(''); }
This works, but the follow-up question asks: can you do it without converting to a string? That eliminates the extra memory from string allocation and avoids character-by-character comparison.
Why avoid strings? String conversion allocates O(log n) extra memory and adds overhead. A pure numeric approach uses O(1) space and gives us an elegant mathematical solution.
The key idea: you don't need to reverse the entire number. Just reverse the second half and compare it to the first half. When the reversed portion grows to equal or exceed the remaining portion, you've crossed the middle.
For the number 1221, pop digits from the right and push them onto a reversed number. Stop when reversed >= x.
Why only half? Reversing the entire number risks integer overflow for values near Integer.MAX_VALUE. By only reversing half, the reversed portion is at most the square root of the original — safely within integer range.
For 12321 (5 digits), the reversed half overshoots by one digit. We simply discard the middle digit by comparing x == reversed / 10.
Let's trace through the algorithm step by step with x = 123321.
The loop condition x > reversed is what makes this work. Each iteration, x shrinks (loses its last digit) and reversed grows (gains that digit). The moment reversed catches up, we've processed exactly half the digits.
Before entering the loop, we handle special cases with a single guard clause:
x < 0.x % 10 == 0.x % 10 == 0 && x != 0 explicitly allows it through. The loop doesn't execute and reversed == x == 0.// Two cases that are immediately NOT palindromes: // 1. Negative numbers (the '-' sign breaks symmetry) // 2. Numbers ending in 0 (except 0 itself, since no leading zeros) if (x < 0 || (x % 10 == 0 && x != 0)) return false;
// Two cases that are immediately NOT palindromes: // 1. Negative numbers (the '-' sign breaks symmetry) // 2. Numbers ending in 0 (except 0 itself, since no leading zeros) if x < 0 || (x%10 == 0 && x != 0) { return false }
# Two cases that are immediately NOT palindromes: # 1. Negative numbers (the '-' sign breaks symmetry) # 2. Numbers ending in 0 (except 0 itself, since no leading zeros) if x < 0 or (x % 10 == 0 and x != 0): return False
// Two cases that are immediately NOT palindromes: // 1. Negative numbers (the '-' sign breaks symmetry) // 2. Numbers ending in 0 (except 0 itself, since no leading zeros) if x < 0 || (x % 10 == 0 && x != 0) { return false; }
// Two cases that are immediately NOT palindromes: // 1. Negative numbers (the '-' sign breaks symmetry) // 2. Numbers ending in 0 (except 0 itself, since no leading zeros) if (x < 0 || (x % 10 === 0 && x !== 0)) return false;
class Solution { public boolean isPalindrome(int x) { // Negative numbers are never palindromes // Numbers ending in 0 can't be palindromes (no leading zeros) // Exception: 0 itself IS a palindrome if (x < 0 || (x % 10 == 0 && x != 0)) return false; int reversed = 0; // Pop digits from x, push onto reversed // Stop when reversed has "caught up" to x (processed half the digits) while (x > reversed) { reversed = reversed * 10 + x % 10; // push last digit of x x /= 10; // pop last digit from x } // Even length: x == reversed (e.g. 1221 → x=12, rev=12) // Odd length: x == reversed / 10 (e.g. 12321 → x=12, rev=123) // The middle digit doesn't affect palindrome check return x == reversed || x == reversed / 10; } }
func isPalindrome(x int) bool { // Negative numbers are never palindromes // Numbers ending in 0 can't be palindromes (no leading zeros) // Exception: 0 itself IS a palindrome if x < 0 || (x%10 == 0 && x != 0) { return false } reversed := 0 // Pop digits from x, push onto reversed // Stop when reversed has "caught up" to x (processed half the digits) for x > reversed { reversed = reversed*10 + x%10 // push last digit of x x /= 10 // pop last digit from x } // Even length: x == reversed (e.g. 1221 → x=12, rev=12) // Odd length: x == reversed / 10 (e.g. 12321 → x=12, rev=123) return x == reversed || x == reversed/10 }
class Solution: def is_palindrome(self, x: int) -> bool: # Negative numbers are never palindromes # Numbers ending in 0 can't be palindromes (no leading zeros) # Exception: 0 itself IS a palindrome if x < 0 or (x % 10 == 0 and x != 0): return False reversed_half = 0 # Pop digits from x, push onto reversed_half # Stop when reversed_half has "caught up" to x (processed half the digits) while x > reversed_half: reversed_half = reversed_half * 10 + x % 10 # push last digit of x x //= 10 # pop last digit from x # Even length: x == reversed_half (e.g. 1221 → x=12, rev=12) # Odd length: x == reversed_half // 10 (e.g. 12321 → x=12, rev=123) # The middle digit doesn't affect palindrome check return x == reversed_half or x == reversed_half // 10
impl Solution { pub fn is_palindrome(x: i32) -> bool { // Negative numbers are never palindromes // Numbers ending in 0 can't be palindromes (no leading zeros) // Exception: 0 itself IS a palindrome if x < 0 || (x % 10 == 0 && x != 0) { return false; } let mut x = x; let mut reversed = 0; // Pop digits from x, push onto reversed // Stop when reversed has "caught up" to x (processed half the digits) while x > reversed { reversed = reversed * 10 + x % 10; // push last digit of x x /= 10; // pop last digit from x } // Even length: x == reversed (e.g. 1221 → x=12, rev=12) // Odd length: x == reversed / 10 (e.g. 12321 → x=12, rev=123) x == reversed || x == reversed / 10 } }
function isPalindrome(x: number): boolean { // Negative numbers are never palindromes // Numbers ending in 0 can't be palindromes (no leading zeros) // Exception: 0 itself IS a palindrome if (x < 0 || (x % 10 === 0 && x !== 0)) return false; let reversed = 0; // Pop digits from x, push onto reversed // Stop when reversed has "caught up" to x (processed half the digits) while (x > reversed) { reversed = reversed * 10 + x % 10; // push last digit of x x = Math.floor(x / 10); // pop last digit from x } // Even length: x === reversed (e.g. 1221 → x=12, rev=12) // Odd length: x === reversed / 10 (e.g. 12321 → x=12, rev=123) // The middle digit doesn't affect palindrome check return x === reversed || x === Math.floor(reversed / 10); }
Only three operations inside the loop: modulo to extract, multiply-and-add to build, integer divide to shrink. No strings, no arrays, no extra memory. Pure arithmetic elegance.
Enter any integer and step through the half-reversal algorithm. Watch x shrink from the right while reversed grows.
We process roughly half the digits of the number. Since a number n has log₁₀(n) digits, we do about log₁₀(n) / 2 iterations -- which is O(log₁₀ n). Each iteration performs one modulo, one multiplication, and one integer division, all O(1). Only a single integer variable (reversed) is used regardless of input size.
Converting the integer to a string produces log10(n) characters, then reversing and comparing scans them all. The string itself and its reversed copy each require O(log n) auxiliary memory.
Extracts every digit via repeated modulo and integer division (log10(n) iterations), building the fully reversed number in a single integer variable. No string allocation needed, but risks overflow for values near Integer.MAX_VALUE.
Processes only half the digits (log10(n) / 2 iterations) by popping digits from x and pushing onto reversed until they meet in the middle. The reversed half never exceeds the square root of the original, eliminating any overflow risk with just one integer variable.
Reversing only half avoids overflow entirely. A full reversal of a number near Integer.MAX_VALUE would overflow the reversed result. By stopping at the midpoint, the reversed half is at most the square root of the original -- safely within integer range, with no overflow check needed.
Review these before coding to avoid predictable interview regressions.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.