9. Palindrome Number

Easy

Math

Companies:

Microsoft

Answered: Dec 2, 2022

View on LeetCode

Problem Description

Given an integer x, return true* if x is a palindrome, and false otherwise.

Examples

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

-2³¹ <= x <= 2³¹ - 1

Follow-up

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

💡 Hints (1)

Solutions

Complexity Analysis

Time Complexity:

O (n)

We need $O(n)$ time to reverse the integer, where n is the number of digits in the integer.

Space Complexity:

O (n)

We need $O(n)$ space to store the reversed integer as a string.

The idea is to reverse the integer and compare it with the original one. If they are the same, then the integer is a palindrome.

Complexity Analysis

Time Complexity:

O (n)

We need $O(n)$ time to compare the characters from both ends, where n is the number of digits in the integer.

Space Complexity:

O (1)

We only need $O(1)$ space to store the pointers and the integer itself.

The idea is to use two pointers to compare characters from both ends of the integer. We start with the left pointer at the beginning of the integer and the right pointer at the end of the integer. We compare the characters at both pointers, if they are not the same, then the integer is not a palindrome. If they are the same, we move the left pointer to the right and the right pointer to the left until they meet in the middle.

Complexity Analysis

Time Complexity:

O (n)

We need $O(n)$ time to reverse the integer, where n is the number of digits in the integer.

Space Complexity:

O (1)

We only need $O(1)$ space to store the reversed integer and the original integer itself.

The idea is to reverse the entire integer and compare it with the original one. We can use a while loop to reverse the digits of the integer. We get the last digit of the integer and add it to the reversed number, then we remove the last digit from the integer. After we have reversed the entire integer, we check if it is equal to the original integer.

Complexity Analysis

Time Complexity:

O (l o g_{10} (n))

We need $O(log_{10}(n)$ ) time to reverse half of the integer, where n is the number of digits in the integer.

Space Complexity:

O (1)

We only need $O(1)$ space to store the reversed half and the integer itself.

The idea is to reverse half of the integer and compare it with the other half. We only need to reverse half of the integer because if the integer is a palindrome, then the first half should be the same as the second half. We can use a while loop to reverse the digits of the integer until we have reversed half of the digits. If the integer has an odd number of digits, we can get rid of the middle digit by reversed_half // 10.

Complexity Analysis

Time Complexity:

O (l o g_{10} (n))

We need $O(log_{10}(n)$ ) time to compare the leading and trailing digits, where n is the number of digits in the integer.

Space Complexity:

O (1)

We only need $O(1)$ space to store the divisor and the integer itself.

The idea is to compare the leading and trailing digits of the integer. We can find the largest divisor to extract the leading digit. We then compare the leading and trailing digits, if they are not the same, then the integer is not a palindrome. If they are the same, we remove the leading and trailing digits and repeat the process until we have compared all digits.

Conclusion

Approach	Time Complexity	Space Complexity	Advantages	Disadvantages
Reverse and Compare string	$O(n)$	$O(n)$	Simple to write and understand	⚠️ Requires extra space for the string
Two Pointers	$O(n)$	$O(1)$	Minimal space usage by comparing characters	⚠️ Still requires converting the integer to a string
Reverse Entire Number	$O(n)$	$O(1)$	Solves mathematically without string conversion	Potential for integer overflow when reversing
Reverse Half of the Number	$O(log_{10}(n)$ )	$O(1)$	Avoids overflow by reversing only half the digits	Slightly more complex logic for odd-length numbers
Leading–Trailing Digit Comparison	$O(log_{10}(n)$ )	$O(1)$	Compares digits directly from both ends	Uses extra division operations

The optimal approach for this problem is Solution 4: Reverse Half of the Number, which achieves $O(log_{10}(n)$ ) time complexity and $O(1)$ space complexity. By only reversing the second half of the integer and comparing it to the first half, this method avoids both string allocation and potential integer overflow issues.

Examples

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.

Solutions

lines
1class Solution:
  def isPalindrome(self, x: int) -> bool:
      # reverse the integer and compare with the original one
      return str(x) == str(x)[::-1]

Complexity Analysis

Time Complexity:

O (n)

We need $O(n)$ time to reverse the integer, where n is the number of digits in the integer.

Space Complexity:

O (n)

We need $O(n)$ space to store the reversed integer as a string.

The idea is to reverse the integer and compare it with the original one. If they are the same, then the integer is a palindrome.

lines
1class Solution:
  def isPalindrome(self, x: int) -> bool:
      # edge cases: negative numbers and numbers that end with 0 (except for 0 itself) cannot be palindromes
      if x < 0 or (x % 10 == 0 and x != 0):
          return False
6
      # initialize two pointers to compare characters from both ends
      left, right = 0, len(str(x)) - 1
9
      # compare the characters from both ends until they meet in the middle
      while left < right:
          if str(x)[left] != str(x)[right]:
              return False
14
          left += 1
          right -= 1
17
      return True

Complexity Analysis

Time Complexity:

O (n)

We need $O(n)$ time to compare the characters from both ends, where n is the number of digits in the integer.

Space Complexity:

O (1)

We only need $O(1)$ space to store the pointers and the integer itself.

lines
1class Solution:
  def isPalindrome(self, x: int) -> bool:
      # edge cases: negative numbers and numbers that end with 0 (except for 0 itself) cannot be palindromes
      if x < 0 or (x % 10 == 0 and x != 0):
          return False
6
      revered_x = 0
      original_x = x
9
      while x > 0:
          # get the last digit of x and add it to the reversed number
          revered_x = revered_x * 10 + (x % 10)
          # remove the last digit from x
          x //= 10
15
      # check if the original number is equal to the reversed number
      return original_x == revered_x

Complexity Analysis

Time Complexity:

O (n)

We need $O(n)$ time to reverse the integer, where n is the number of digits in the integer.

Space Complexity:

O (1)

We only need $O(1)$ space to store the reversed integer and the original integer itself.

lines
1class Solution:
  def isPalindrome(self, x: int) -> bool:
      # edge cases: negative numbers and numbers that end with 0 (except for 0 itself) cannot be palindromes
      if x < 0 or (x % 10 == 0 and x != 0):
          return False
6
      reversed_half = 0
8
      # we only need to reverse half of the integer, because if the integer is a palindrome, then the first half should be the same as the second half
      while x > reversed_half:
          reversed_half = reversed_half * 10 + x % 10
          x //= 10
13
      # if the integer has an odd number of digits, we can get rid of the middle digit by reversed_half // 10
      return x == reversed_half or x == reversed_half // 10

Complexity Analysis

Time Complexity:

O (l o g_{10} (n))

We need $O(log_{10}(n)$ ) time to reverse half of the integer, where n is the number of digits in the integer.

Space Complexity:

O (1)

We only need $O(1)$ space to store the reversed half and the integer itself.

lines
1class Solution:
  def isPalindrome(self, x: int) -> bool:
      # edge cases: negative numbers and numbers that end with 0 (except for 0 itself) cannot be palindromes
      if x < 0 or (x % 10 == 0 and x != 0):
          return False
6
      divisor = 1
8
      # find the largest divisor to extract the leading digit
      while (x // divisor) >= 10:
          divisor *= 10
12
      while x != 0:
          # extract the leading and trailing digits
          left = x // divisor
          right = x % 10
17
          # if the leading and trailing digits are not the same, it's not a palindrome
          if left != right:
              return False
21
          # remove the leading and trailing digits
          x = (x % divisor) // 10
          divisor //= 100
25
      return True

Complexity Analysis

Time Complexity:

O (l o g_{10} (n))

We need $O(log_{10}(n)$ ) time to compare the leading and trailing digits, where n is the number of digits in the integer.

Space Complexity:

O (1)

We only need $O(1)$ space to store the divisor and the integer itself.

Conclusion

Approach	Time Complexity	Space Complexity	Advantages	Disadvantages
Reverse and Compare string	$O(n)$	$O(n)$	Simple to write and understand	⚠️ Requires extra space for the string
Two Pointers	$O(n)$	$O(1)$	Minimal space usage by comparing characters	⚠️ Still requires converting the integer to a string
Reverse Entire Number	$O(n)$	$O(1)$	Solves mathematically without string conversion	Potential for integer overflow when reversing
Reverse Half of the Number	$O(log_{10}(n)$ )	$O(1)$	Avoids overflow by reversing only half the digits	Slightly more complex logic for odd-length numbers
Leading–Trailing Digit Comparison	$O(log_{10}(n)$ )	$O(1)$	Compares digits directly from both ends	Uses extra division operations

Problem Description

Examples

Example 1

Example 2

Example 3

Constraints

Follow-up

💡 Hints (1)

Solutions

Solution 1: Reverse and Compare string

Complexity Analysis

Explanation

Solution 2: Two Pointers

Complexity Analysis

Explanation

Solution 3: Reverse Entire Number

Complexity Analysis

Explanation

Solution 4: Reverse Half of the Number

Complexity Analysis

Explanation

Solution 5: Leading–Trailing Digit Comparison

Complexity Analysis

Explanation

Conclusion

Problem Description

Examples

Example 1

Example 2

Example 3

Constraints

Follow-up

💡 Hints (1)

Solutions

Solution 1: Reverse and Compare string

Complexity Analysis

Explanation

Solution 2: Two Pointers

Complexity Analysis

Explanation

Solution 3: Reverse Entire Number

Complexity Analysis

Explanation

Solution 4: Reverse Half of the Number

Complexity Analysis

Explanation

Solution 5: Leading–Trailing Digit Comparison

Complexity Analysis

Explanation

Conclusion