Numerical symmetry check: Palindrome integer without string conversion

You're in a phone screen with Apple, and the interviewer opens with something deceptively simple: "Can you tell me if an integer is a palindrome? Oh, and don't convert it to a string." This problem, also known as "Palindrome Number" on other platforms, strips away the convenience of string manipulation and forces you to think in pure arithmetic. It's a favorite warm-up at companies like Apple, Adobe, Google, and Amazon because it tests edge case awareness and mathematical reasoning in under fifteen minutes.

TL;DR

Check if an integer reads the same forwards and backwards by reversing only the second half of its digits. Extract digits from the end using x % 10, build the reversed half, and stop when the reversed portion meets or exceeds the remaining digits. Compare the two halves, dividing the reversed half by 10 for odd-length numbers. This runs in O(log n) time and O(1) space with no overflow risk.

Why This Problem Matters

Palindrome checking on integers sounds trivial if you can use String.valueOf(x), but the "no string conversion" constraint is what makes it a legitimate interview question. It tests whether you can decompose a number digit by digit using modular arithmetic and whether you think about overflow, negative numbers, and trailing zeros. These are the kinds of edge cases that separate a quick accept from a frustrating debug cycle.

Understanding the Problem

Given an integer x, return true if x reads the same forwards and backwards, and false otherwise.

Examples:

• isPalindrome(121) returns true (121 reversed is 121)
• isPalindrome(-121) returns false (-121 reversed would be "121-", not valid)
• isPalindrome(10) returns false (10 reversed is 01, which is 1)
• isPalindrome(1) returns true

Constraints: x is in the range [-2^31, 2^31 - 1].

Edge Cases Worth Noting

Before diving into the algorithm, there are a few inputs that deserve special attention:

1. Negative numbers: Always non-palindromes. The minus sign has no counterpart at the end.
2. Numbers ending in zero: A number like 100 would need a leading zero to be a palindrome, which integers don't have. The exception is zero itself.
3. Single digit numbers: Always palindromes (0 through 9).

The Naive Approach and Its Problem

The first instinct is to fully reverse the integer and compare it to the original. That works, but reversing a number near Integer.MAX_VALUE (2,147,483,647) can overflow. For example, reversing 2,147,483,647 gives 7,463,847,412, which exceeds the 32-bit signed integer range.

You could add overflow checks, but there's a cleaner path.

The Half-Reversal Strategy

Instead of reversing the entire number, reverse only the second half. If the number is a palindrome, the first half and the reversed second half will match.

The loop condition is the key: keep extracting digits from the end until the reversed portion is greater than or equal to what remains. At that point, you've crossed the midpoint.

For an odd-length palindrome like 12321:

The loop stops when reversedHalf (123) exceeds x (12). Since the middle digit (3) sits in reversedHalf, we check x == reversedHalf / 10, which gives 12 == 12. Palindrome confirmed.

For an even-length palindrome like 1221:

Here the halves match directly: x == reversedHalf gives 12 == 12.

For a non-palindrome like 123:

The loop stops when reversedHalf (32) exceeds x (1). Neither 1 == 32 nor 1 == 3 holds, so it returns false.

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {
  public boolean isPalindrome(int x) {
    // Negative numbers and numbers ending in zero (except zero itself) are never palindromes
    if (x < 0 || (x % 10 == 0 && x != 0)) {
      return false;
    }

    int reversedHalf = 0;
    while (x > reversedHalf) {
      reversedHalf = reversedHalf * 10 + x % 10;
      x /= 10;
    }

    // For even-length: x == reversedHalf
    // For odd-length: x == reversedHalf / 10 (drops the middle digit)
    return x == reversedHalf || x == reversedHalf / 10;
  }
}

Walking through the code:

1. Quick rejection: If x is negative, it can't be a palindrome. If x ends in zero but isn't zero, it can't be a palindrome either (no leading zeros allowed).
2. Half-reversal loop: Each iteration peels the last digit off x with x % 10 and appends it to reversedHalf. Then x shrinks by one digit via integer division. The loop runs until reversedHalf catches up to or passes x.
3. Final comparison: For even-length numbers, the halves should be equal. For odd-length numbers, reversedHalf contains one extra digit (the middle one), so we divide it by 10 before comparing.

Complexity Analysis

Time Complexity: O(log n)

Each loop iteration removes one digit from x, and we only process half the digits before stopping. The total number of digits in x is floor(log10(x)) + 1, so the loop runs roughly log10(x) / 2 times.

Space Complexity: O(1)

We use a single integer variable (reversedHalf) regardless of the input size. No arrays, no strings, no recursion.

Why Not Full Reversal?

Full reversal is also O(log n) time and O(1) space, but it needs overflow protection. The half-reversal approach avoids overflow entirely because reversedHalf never exceeds the original number's magnitude. It's a strictly better solution for 32-bit integers.

Common Pitfalls

1. Forgetting the trailing-zero check: Without the x % 10 == 0 && x != 0 guard, inputs like 10, 100, or 1000 would incorrectly return true. The loop would terminate with x = 0 and reversedHalf = 1, and 0 != 1 catches it, but only by accident in some implementations.

2. Using x != reversedHalf as the loop condition: This overshoots for even-length numbers. The correct condition is x > reversedHalf, which stops right at the midpoint.

3. Forgetting odd-length handling: If you only check x == reversedHalf, odd-length palindromes like 12321 will fail because x (12) will never equal reversedHalf (123).

4. Converting to a string: The constraint specifically asks you not to. In an interview, using String.valueOf() or Integer.toString() means you've missed the point of the question.

Interview Tips

When you encounter this problem in a phone screen or on-site:

• State the edge cases upfront: Mention negative numbers, trailing zeros, and single digits before you start coding. This signals thoroughness.
• Explain why half-reversal beats full reversal: The overflow argument is a strong differentiator. Most candidates go straight to full reversal.
• Trace through an example: Pick an odd-length palindrome like 12321 and walk through each loop iteration on the whiteboard. It makes the midpoint logic obvious.
• Mention the string approach as a tradeoff: Acknowledge that converting to a string is O(n) time and O(n) space, and explain why the mathematical approach is preferable.

Key Takeaways

• Reversing only half the digits avoids integer overflow entirely, making it the preferred approach for 32-bit integer palindrome checks.
• The loop condition x > reversedHalf naturally detects the midpoint: for even-length numbers the halves are equal, for odd-length numbers reversedHalf has one extra digit.
• Quick-reject negative numbers and trailing-zero numbers before entering the loop. Zero is the only number ending in zero that's a palindrome.
• This pattern of digit extraction with % 10 and / 10 shows up in many integer manipulation problems (reverse integer, count digits, digit sum), so it's worth internalizing.

Related Problems and Practice

Once you're comfortable with palindrome integers, these problems build on similar digit-manipulation skills:

• Digit Reversal with Overflow Guard (reverse an integer while handling overflow)
• Palindrome Tester (string-based palindrome checking)
• Counting Set Bits in Binary (similar decomposition loop, but in base 2)

This problem and hundreds of others are available on Firecode, where over 50,000 engineers have prepared for technical interviews at companies like Apple, Google, and Amazon. The spaced repetition system ensures you retain these patterns long after your first solve.

Solutions in Other Languages

Python

class Solution:
    def is_palindrome(self, x: int) -> bool:
        if x < 0 or (x % 10 == 0 and x != 0):
            return False

        reversed_half = 0
        while x > reversed_half:
            reversed_half = reversed_half * 10 + x % 10
            x //= 10

        return x == reversed_half or x == reversed_half // 10

Python's arbitrary-precision integers mean overflow is never a concern, but the half-reversal approach is still preferred for its efficiency and for demonstrating the technique interviewers expect.

JavaScript

class Solution {
  isPalindrome(x) {
    if (x < 0 || (x % 10 === 0 && x !== 0)) {
      return false;
    }

    let reversedHalf = 0;
    while (x > reversedHalf) {
      reversedHalf = reversedHalf * 10 + x % 10;
      x = Math.floor(x / 10);
    }

    return x === reversedHalf || x === Math.floor(reversedHalf / 10);
  }
}

Note the use of Math.floor for integer division, since JavaScript's / operator returns a float.

TypeScript

class Solution {
  isPalindrome(x: number): boolean {
    if (x < 0) return false;
    let original = x;
    let reversed = 0;
    while (x > 0) {
      let digit = x % 10;
      reversed = reversed * 10 + digit;
      x = Math.floor(x / 10);
    }
    return original === reversed;
  }
}

The TypeScript solution uses full reversal since JavaScript numbers are 64-bit floats with safe integer range up to 2^53, making overflow a non-issue in practice.

C++

class Solution {
public:
  bool isPalindrome(int x) {
    if (x < 0 || (x % 10 == 0 && x != 0)) {
      return false;
    }

    int reversedHalf = 0;
    while (x > reversedHalf) {
      reversedHalf = reversedHalf * 10 + x % 10;
      x /= 10;
    }

    return x == reversedHalf || x == reversedHalf / 10;
  }
};

Go

func (s *Solution) IsPalindrome(x int) bool {
    if x < 0 {
        return false
    }

    original := x
    reversed := 0

    for x != 0 {
        pop := x % 10
        x /= 10

        if reversed > (1<<31-1)/10 || (reversed == (1<<31-1)/10 && pop > 7) {
            return false
        }

        reversed = reversed*10 + pop
    }

    return original == reversed
}

The Go solution uses full reversal with explicit overflow protection, which is idiomatic for Go's strict integer handling.

Scala

class Solution {
  def isPalindrome(x: Int): Boolean = {
    if (x < 0) return false
    var original = x
    var reversed = 0
    while (original != 0) {
      val pop = original % 10
      original /= 10
      if (reversed > (Int.MaxValue - pop) / 10) return false
      reversed = reversed * 10 + pop
    }
    x == reversed
  }
}

Kotlin

class Solution {
  fun isPalindrome(x: Int): Boolean {
    if (x < 0 || (x % 10 == 0 && x != 0)) {
      return false
    }

    var reversedHalf = 0
    var num = x
    while (num > reversedHalf) {
      reversedHalf = reversedHalf * 10 + num % 10
      num /= 10
    }

    return num == reversedHalf || num == reversedHalf / 10
  }
}

Kotlin requires a mutable copy (var num = x) since function parameters are val by default.

Swift

class Solution {
    func isPalindrome(_ x: Int) -> Bool {
        if x < 0 || (x % 10 == 0 && x != 0) {
            return false
        }

        var reversedHalf = 0
        var num = x
        while num > reversedHalf {
            reversedHalf = reversedHalf * 10 + num % 10
            num /= 10
        }

        return num == reversedHalf || num == reversedHalf / 10
    }
}

Ruby

class Solution
  def is_palindrome(x)
    return false if x < 0 || (x % 10 == 0 && x != 0)

    reversed_half = 0
    while x > reversed_half
      reversed_half = reversed_half * 10 + x % 10
      x /= 10
    end

    x == reversed_half || x == reversed_half / 10
  end
end

Rust

impl Solution {
    pub fn is_palindrome(&self, mut x: i32) -> bool {
        if x < 0 || (x % 10 == 0 && x != 0) {
            return false;
        }

        let mut reversed_half = 0;
        while x > reversed_half {
            reversed_half = reversed_half * 10 + x % 10;
            x /= 10;
        }

        x == reversed_half || x == reversed_half / 10
    }
}

Rust's mut parameter binding allows modifying x directly. The i32 type matches the 32-bit constraint.

C#

public class Solution {
    public bool IsPalindrome(int x) {
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

        var reversedHalf = 0;
        while (x > reversedHalf) {
            reversedHalf = reversedHalf * 10 + x % 10;
            x /= 10;
        }

        return x == reversedHalf || x == reversedHalf / 10;
    }
}

Dart

class Solution {
  bool isPalindrome(int x) {
    if (x < 0 || (x % 10 == 0 && x != 0)) {
      return false;
    }

    int reversedHalf = 0;
    while (x > reversedHalf) {
      reversedHalf = reversedHalf * 10 + x % 10;
      x = x ~/ 10;
    }

    return x == reversedHalf || x == reversedHalf ~/ 10;
  }
}

Dart uses the ~/ operator for integer division, similar to Python's //.

PHP

class Solution {
    public function isPalindrome(int $x): bool {
        if ($x < 0 || ($x % 10 === 0 && $x !== 0)) {
            return false;
        }

        $reversedHalf = 0;
        while ($x > $reversedHalf) {
            $reversedHalf = $reversedHalf * 10 + $x % 10;
            $x = intdiv($x, 10);
        }

        return $x === $reversedHalf || $x === intdiv($reversedHalf, 10);
    }
}

PHP uses intdiv() for integer division since the / operator returns a float.