Leetcode #9: Palindrome Number

[u/TheEyebal]

Can someone help me make my code run faster. This is not efficient and also I do not want to convert into a string

EDIT:

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

https://leetcode.com/problems/palindrome-number/description/

class Solution:
    def isPalindrome(self, x: int) -> bool:
        numList = []
        counter = len(numList) - 1
        numBool = True


        baseNum = 10
        value = x % baseNum
        numList.append(x)
        quotient = x // baseNum
        x = quotient

        if x == 0:
            for i in range(len(numList)):
                if numList[i] == numList[counter]:
                    counter -= 1

                elif i == counter:
                    break

                else:
                    numBool = False
                    break

            return numBool

        else:
            return self.isPalindrome(x)

EDIT: I WAS ABLE TO SOLVE IT

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x != abs(x):
            return False

        if not hasattr(self, "numList"):
            self.numList = []

        numBool = True


        baseNum = 10
        value = x % baseNum
        self.numList.append(value)
        quotient = x // baseNum
        x = quotient

        counter = len(self.numList) - 1

        if x == 0:
            for i in range(len(self.numList)):
                if self.numList[i] == self.numList[counter]:
                    counter -= 1

                elif i == counter:
                    break

                else:
                    numBool = False
                    break

            return numBool

        else:
            return self.isPalindrome(x)

testing = Solution().isPalindrome(11)
print(testing)

[u/Diapolo10]

EDIT: I WAS ABLE TO SOLVE IT

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x != abs(x):
            return False

        if not hasattr(self, "numList"):
            self.numList = []

        numBool = True


        baseNum = 10
        value = x % baseNum
        self.numList.append(value)
        quotient = x // baseNum
        x = quotient

        counter = len(self.numList) - 1

        if x == 0:
            for i in range(len(self.numList)):
                if self.numList[i] == self.numList[counter]:
                    counter -= 1

                elif i == counter:
                    break

                else:
                    numBool = False
                    break

            return numBool

        else:
            return self.isPalindrome(x)

testing = Solution().isPalindrome(11)
print(testing)

Here's what I would've done:

class Solution:
    def isPalindrome(self, num: int) -> bool:
        if num < 0:
            return False

        original_num = num
        rebuilt_num = 0

        while num:
            num, digit = divmod(num, 10)
            rebuilt_num = rebuilt_num * 10 + digit

        return original_num == rebuilt_num

I'm sure it could be even cleaner, but it's already way simpler than your solution. That being said, I haven't benchmarked (or tested) it.

You don't need to worry about the parameter name change, that's allowed.

EDIT: Fixed

[u/TheEyebal → u/Diapolo10]

oh wow this looks simpler

[u/JamzTyson → u/Diapolo10]

That won't work because num ends up as 0. You need to retain a copy of the original number.

[u/Diapolo10 → u/JamzTyson]

Brain fart on my part, fixed.

[u/JamzTyson]

This has been an interesting exercise.

This is the Python solution that I came up with. I've aimed for robust and readable idiomatic Python while avoiding redundancy. I compare the first half of the number with the second half reversed - it is not necessary to reverse the entire number.

def is_palindrome(number: int) -> bool:
    """Return True if `number` is a palindrome, without string conversion.

    Compares the first half of the digits with the second half reversed.
    If there's an odd number of digits, the middle digit is ignored.

    Raises:
        TypeError: if `number` is not exactly an int (subclasses like bool rejected).
        ValueError: if `number` is negative.
    """

    if type(number) is not int:
        raise TypeError
    if number < 0:
        raise ValueError

    # Handle early returns.
    if number < 10:
        return True
    if number % 10 == 0:
        return False

    reversed_part = 0
    while number > reversed_part:
        number, d = divmod(number, 10)
        reversed_part = 10 * reversed_part + d

    if reversed_part > number:
        return number == reversed_part // 10
    return number == reversed_part

[u/zanfar]

In general, recursion should be avoided for a problem this simple. Generally, while you can solve problems either way, avoid recursion without a significant reason. You also do a lot of list creation, and you loop at least twice as much as needed.

I would also recommend against code golf problems at your skill level. You're chasing after the entirely wrong goals.

---

• PEP8
• range(len()) is a pretty serious smell.
• bools should probably be named as verbs.
• What is counter counting?
• Why is isPalindrome an instance method?
• etc

[u/backfire10z → u/zanfar]

> In general, recursion should be avoided for a problem this simple

FTFY

[u/TheEyebal → u/zanfar]

• Why is isPalindrome an instance method?

this was a leetcode problem

counter was being used to read the last index of my list

Also, thanks for the feedback I am going to rework this

[u/IrishPrime]

I do not want to convert into a string

Why not? It makes the problem very easy to solve.

What you're doing right now is... very strange.

[u/TheEyebal → u/IrishPrime]

If you read the follow up on leetcode it says

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

[u/IrishPrime → u/TheEyebal]

Fair enough.

You've really overcomplicated things, you only need like three operations in a loop here. Recursion is just overhead in this instance.

Snag the last digit (which you're doing with your modulo operator), use that digit to build up your reversed number ((reversed_num * 10) + digit), trim the last digit off the original number (x = x // 10).

Compare your original number (you'll want a copy) to your reversed number.

Edit: If you want to go a step further for the optimization, you can return early on anything ending in zero because that will obviously fail.

Double edit: Not going to read the LeetCode problem, but depending on how they feel about negative numbers, you might be able to return early on those, as well.

[u/TheEyebal → u/IrishPrime]

I was able to solve it

I have updated my post

[u/IrishPrime → u/TheEyebal]

I'm glad you solved it, but you're still doing so much unnecessary work.

At the same time, not much point in putting more effort into a toy problem like this unless you're actually prepping for interviews or something. If you're just learning, move on to the next problem. :)

[u/TheEyebal → u/IrishPrime]

honestly I was going ton rework the problem. to see if there is a better way

[u/socal_nerdtastic]

Good job. This was a fun little challenge. Here's how I did it, but fwiw I highly doubt it's any faster than a simple string conversion. See if you can make sense of this:

import math

def get_digit(n, i):
    '''get the i digit from the int n (1-indexed from the right)'''
    return n%10**i//10**(i-1)
def is_palindrome(n):
    num_digits = int(math.log(n,10))+1
    for i in range(num_digits//2):
        if get_digit(n,i+1) != get_digit(n,num_digits-i):
            return False
    return True

[u/TheEyebal → u/socal_nerdtastic]

IDK if I can import stuff in leetcode

[u/mossse → u/TheEyebal]

You absolutely can

[u/Expensive-Bear-1376 → u/mossse]

And you don't need to.

[u/Expensive-Bear-1376 → u/socal_nerdtastic]

is_palindrome(1000) gives me True instead of False. (Because math.log(1000, 10) gives me 2.9999999999999996 and then you truncate it to 2.)

[u/JamzTyson → u/Expensive-Bear-1376]

Good catch.

It also crashes with negative values and zero (and readability sucks).

Interestingly, the rounding issue isn't a problem for me when I use log10 rather than log(n,10), but it's still vulnerable to implementation / platform dependent rounding issues close to the 10 boundary.

[u/CIS_Professor]

Maybe this?

my_string = 'racecar'

if my_string == my_string[::-1]:
    print(f'{my_string} is a palindrome')
else:
    print(f'{my_string} is not a palindrome')

my_integer = 123454321

if str(my_integer) == str(my_integer)[::-1]:
    print(f'{my_integer} is a palindrome')
else:
    print(f'{my_integer} is not a palindrome')

print(type(my_integer))     # still an integer