Palindrome Number
Palindrome Number is a easy arrays & hashing problem solved with the math / number theory pattern.
The best approach, optimal (reverse half of the digits), runs in O(log x) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (compare as a string) up.
Problem
Given an integer x, return true if its decimal digits read the same from left to right as from right to left, and false otherwise.
The minus sign of a negative number counts as part of how it is written, so -5 reads as 5- backwards and is not a palindrome.
Can you solve it without converting the number to a string?
Examples
Example 1
- Input
x = 4774- Output
true- Why
- Read right to left, the digits are still 4, 7, 7, 4.
Example 2
- Input
x = -626- Output
false- Why
- Backwards it reads 626-, which is not the same text.
Example 3
- Input
x = 320- Output
false- Why
- Backwards it reads 023; a number cannot start with 0, so the two readings differ.
Constraints
-2^31 <= x <= 2^31 - 1
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 15 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (compare as a string) | O(d) | O(d) |
| Optimal (reverse half of the digits) | O(log x) | O(1) |
1Brute force (compare as a string)
O(d)d is the number of digits (at most 11 with the sign); each is compared once.O(d)The string copy holds every digit.Turn the number into its decimal string and check it with two pointers moving inward from both ends.
- Convert x to a string s (a negative number keeps its '-' sign, so it fails automatically).
- Set i = 0 and j = s.length - 1.
- While i < j, return false if s[i] != s[j]; otherwise move both pointers inward.
- Return true.
class Solution {
public boolean isPalindrome(int x) {
String s = Integer.toString(x);
int i = 0, j = s.length() - 1;
while (i < j) {
if (s.charAt(i) != s.charAt(j)) return false;
i++;
j--;
}
return true;
}
}class Solution:
def isPalindrome(self, x: int) -> bool:
s = str(x)
i, j = 0, len(s) - 1
while i < j:
if s[i] != s[j]:
return False
i += 1
j -= 1
return Trueclass Solution {
public:
bool isPalindrome(int x) {
string s = to_string(x);
int i = 0, j = (int)s.size() - 1;
while (i < j) {
if (s[i] != s[j]) return false;
i++;
j--;
}
return true;
}
};function isPalindrome(x) {
const s = String(x);
let i = 0, j = s.length - 1;
while (i < j) {
if (s[i] !== s[j]) return false;
i++;
j--;
}
return true;
}2Optimal (reverse half of the digits)
O(log x)Each loop step removes one digit, and the loop stops after about half of the digits.O(1)Only two integer variables.Work only with arithmetic. Pop digits off the end of x and push them onto rev. When rev is no longer smaller than what remains of x, half of the digits have moved over. For an even digit count the halves must be equal; for an odd count, drop the middle digit with rev / 10. Because only half the number is ever reversed, nothing can overflow.
- If x < 0, or x ends in 0 but is not 0, return false.
- rev = 0. While x > rev: rev = rev * 10 + x % 10, and x = x / 10.
- Return x == rev || x == rev / 10.
class Solution {
public boolean isPalindrome(int x) {
if (x < 0 || (x % 10 == 0 && x != 0)) return false;
int rev = 0;
while (x > rev) {
rev = rev * 10 + x % 10;
x /= 10;
}
return x == rev || x == rev / 10;
}
}class Solution:
def isPalindrome(self, x: int) -> bool:
if x < 0 or (x % 10 == 0 and x != 0):
return False
rev = 0
while x > rev:
rev = rev * 10 + x % 10
x //= 10
return x == rev or x == rev // 10class Solution {
public:
bool isPalindrome(int x) {
if (x < 0 || (x % 10 == 0 && x != 0)) return false;
int rev = 0;
while (x > rev) {
rev = rev * 10 + x % 10;
x /= 10;
}
return x == rev || x == rev / 10;
}
};function isPalindrome(x) {
if (x < 0 || (x % 10 === 0 && x !== 0)) return false;
let rev = 0;
while (x > rev) {
rev = rev * 10 + (x % 10);
x = Math.floor(x / 10);
}
return x === rev || x === Math.floor(rev / 10);
}Edge cases to test
- Negative numbers are never palindromes because of the leading minus sign
- Numbers ending in 0 (other than 0 itself), like 50 or 1210
- Single-digit numbers, including 0
- Values near the int limit, where a full reversal could overflow
Hints
Hint 1
A negative number can be rejected right away. What about a positive number whose last digit is 0?
Hint 2
You can peel digits off the end with % 10 and / 10 and build the reversed number as you go.
Hint 3
You only need to reverse half of the digits: stop once the reversed part is at least as large as what is left.
FAQ
What is the best time complexity for Palindrome Number?
Optimal (reverse half of the digits) runs in O(log x) time and O(1) extra space. Each loop step removes one digit, and the loop stops after about half of the digits.
Which pattern does Palindrome Number use?
It is a arrays & hashing problem that uses the math / number theory pattern. Other problems with the same pattern: Bulb Switcher, Reaching Points, Water and Jug Problem.
Is there a brute force solution for Palindrome Number?
Yes. Brute force (compare as a string) takes O(d) time and O(d) space. Turn the number into its decimal string and check it with two pointers moving inward from both ends.
Which edge cases should I test for Palindrome Number?
Negative numbers are never palindromes because of the leading minus sign; Numbers ending in 0 (other than 0 itself), like 50 or 1210; Single-digit numbers, including 0; Values near the int limit, where a full reversal could overflow.