I'm checking whether an integer is a palindrome in Python. My recursive version collects digits in a list, but it feels unnecessarily complicated. Is there a faster way without converting the number to a string?
How can I speed up my palindrome number check without converting to a string?
Asked by
u47+clkhold_91
Answers
Reverse the number with arithmetic and compare it to the original. Keep a copy of x, then repeatedly take the last digit with x % 10, add it to a reversed number with reversed * 10 + digit, and remove the digit with x // 10.
Reject negative numbers first. Once the loop finishes, compare the reversed value with the saved original. Zero works too, since both values remain zero. This takes time proportional to the number of digits and doesn't need a list or recursion.
Reply to this answer
You can reverse only the right half. Reject negative numbers and any nonzero number ending in zero. Then move digits from x into a reversed half until x is no larger than that half.
For an even number of digits, the two halves should match. For an odd number, drop the middle digit from the reversed half with integer division by 10 before comparing. Python integers don't overflow, but reversing only half can also help avoid overflow in languages with fixed-width integers.
Reply to this answer
If you want to keep the list approach, append the extracted digit, not x before you remove that digit. A loop can collect the digits, then two indexes can compare the outer pair and move inward until they meet or a pair differs.
Also, keeping the list on self can leave digits from an earlier call on the same object. A local list inside the method avoids that.
Reply to this answer
Add your answer
Answers are reviewed before publication.
x603!regsel_7:
The trailing-zero check needs the exception for zero, since zero itself is a palindrome.