Palindrome Number

Easy Arrays & Hashing Math / Number Theory Original on LeetCode

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.

00:00
Testcase

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.

ApproachTimeSpace
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)

TimeO(d)d is the number of digits (at most 11 with the sign); each is compared once.
SpaceO(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.

  1. Convert x to a string s (a negative number keeps its '-' sign, so it fails automatically).
  2. Set i = 0 and j = s.length - 1.
  3. While i < j, return false if s[i] != s[j]; otherwise move both pointers inward.
  4. 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;
    }
}

2Optimal (reverse half of the digits)

TimeO(log x)Each loop step removes one digit, and the loop stops after about half of the digits.
SpaceO(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.

  1. If x < 0, or x ends in 0 but is not 0, return false.
  2. rev = 0. While x > rev: rev = rev * 10 + x % 10, and x = x / 10.
  3. 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;
    }
}

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.