Katkat
Back

Determine Whether an Integer Is a Palindrome

ByteDanceData Scientist · Technical Screen
MediumData ScientistTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to manipulate integers mathematically to detect palindromic sequences without converting the number into a string, requiring careful handling of edge cases and integer overflow.

Problem Statement

Given an integer x, return true if x is a palindrome, and false otherwise. An integer is a palindrome when it reads the same forward and backward.

For example, 121 is a palindrome, while 123 is not. You must solve this problem without converting the integer into a string.

Function Signature

def is_palindrome(x: int) -> bool:

Constraints

  • -2^31 <= x <= 2^31 - 1
  • Time complexity required: O(log10(n))
  • Space complexity required: O(1)

Examples

Example 1: Input: x = 121 Output: true

Example 2: Input: x = -121 Output: false Explanation: Reading from left to right, it becomes -121. Reading from right to left, it becomes 121-. Therefore, it is not a palindrome.

Example 3: Input: x = 10 Output: false Explanation: Reading 01 from right to left, it is 01, not 10.

Edge Cases

  • Negative numbers (always return false).
  • Numbers ending in zero (e.g., 10, 100).
  • Single-digit numbers (always return true).

Hints

Hint 1

Consider that any negative number cannot be a palindrome due to the presence of the negative sign.

Hint 2

Think about reversing the second half of the number and comparing it to the first half, rather than reversing the entire number, to avoid potential integer overflow.

Hint 3

For a number like 1221, if you reverse the last two digits (21 -> 12), you can check if they match the remaining first half (12).

Follow-up questions

  • How would your approach change if you were allowed to use extra space or string conversion?
  • What specific test cases would you use to verify your logic for integers ending in zero?
  • If the input size were significantly larger than a 64-bit integer, how would that affect your implementation?