Palindrome Number

Q: Is a negative number a palindrome?

No. Read backwards, -121 becomes 121- , and the minus sign has no matching character at the other end. So every negative integer returns false .

Q: What is the time complexity of Palindrome Number?

Both approaches run in O(log x) time, because a number x has about log10(x) digits and each is handled once. The string approach uses O(log x) extra space for the text; the half reversal uses O(1) .

EasyMath and simulation

+10

A number is a palindrome when its digits read the same from left to right and from right to left, like 1221. Given an integer x, return true if it is a palindrome and false otherwise. A negative number never counts, because its minus sign has no partner at the other end.

Function

isPalindrome(x: integer) → boolean

xinteger: the integer to check, possibly negative
Returnsboolean: true if x reads the same in both directions, false otherwise

Constraints

-2³¹ ≤ x ≤ 2³¹-1
Every negative number returns false.

Examples

Input: x = 121
Output: true
Explanation: Read backwards, 121 is still 121, so the answer is true.

Input: x = -121
Output: false
Explanation: Read backwards, -121 becomes 121-, which is a different text, so the answer is false.

Follow-up

Can you solve it without converting the integer to a string?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

A number is a palindrome when it equals its own reverse. As text that is one comparison. Without text, rebuilding the whole reversed number can overflow, so reverse only the second half of the digits and compare it with the first half.

Compare the string with its reverse

Intuition

Write the number as text and compare it with its reverse. Negative numbers need no special case: -121 starts with a minus sign and ends with a digit, so it never equals its reverse 121-.

The text has one character per digit, about log10(x) of them and at most 11 here. The cost is the extra string.

Algorithm

Convert x to a string s.
Reverse s.
Return whether s equals its reverse.

def isPalindrome(x):
    s = str(x)
    # A minus sign sits only at the front, so a negative never matches its reverse.
    return s == s[::-1]

Reverse half of the number

Intuition

x % 10 gives the last digit, and integer division by 10 removes it. Moving digits from the end of x onto a second number half builds the reverse of the digits you removed. Stop once half is at least what is left of x: you have taken half the digits. 1221 ends with x = 12 and half = 12, a palindrome. With an odd digit count half also holds the middle digit: 12321 ends with x = 12 and half = 123, so you compare x with half / 10.

Settle two cases before the loop. A negative number is never a palindrome. A number that ends in 0 would have to start with 0, which only 0 does; without this check, 10 ends with x = 0 and half = 1, and x == half / 10 passes by mistake. half never grows past 6 digits, so it fits any integer type.

Algorithm

If x is negative, or ends in 0 and is not 0, return false.
Set half = 0.
While x > half, set half = half * 10 + x % 10 and divide x by 10 with integer division.
Return true if x == half (even digit count) or x == half / 10 (odd digit count).

def isPalindrome(x):
    if x < 0:
        return False
    original, reversed_num = x, 0
    while x > 0:
        reversed_num = reversed_num * 10 + x % 10
        x //= 10
    return original == reversed_num

Pitfalls and edge cases

Forgetting negatives. In languages whose remainder keeps the sign, reversing -121 gives -121 and the check passes. In Python, where -1 // 10 is -1, a while x != 0 loop never ends.
Not rejecting numbers that end in 0. The half reversal then accepts 10. 0 itself is a palindrome.
Reversing the whole number in a 32-bit integer. The reverse of 2147483647 does not fit.
Using / where the language divides with a fraction. Use Math.floor(x / 10) in JavaScript, // in Python, %/% in R and ~/ in Dart.
Comparing the full reverse with x after the loop has changed x. Keep a copy of the original.

Frequently asked questions3

Is a negative number a palindrome?

No. Read backwards, -121 becomes 121-, and the minus sign has no matching character at the other end. So every negative integer returns false.

Why reverse only half of the number?

Reversing every digit can overflow a 32-bit integer: the reverse of 2147483647 is larger than the largest int. Half of the digits always fits, and the loop does half the work.

What is the time complexity of Palindrome Number?

Both approaches run in O(log x) time, because a number x has about log10(x) digits and each is handled once. The string approach uses O(log x) extra space for the text; the half reversal uses O(1).

def isPalindrome(x):
    # Write code here

Test #1

Test #2

Argument

x = 121

Expected Output

true