CODEWITHSUNDEEP
pythoniterationpalindrome
user9873466
user9873466

Reputation: 115

Check if a number is a palindrome without changing it into string

I'm having trouble with this problem that simply return True of False if a number n, is a palindrome.

Note: wherever I have a ____ indicates where there is a blank that needs to be filled in. There are 2 blank spaces. 

def is_palindrome(n):
    x, y = n, 0
    f = lambda: ____
    while x > 0:
        x, y = ____ , f()
    return y == n

I've spent about an hour on this. I've found out that putting x//10 in the second blank space will allow the function to iterate over the number of digits in n. It then comes down to the function f.

Ideally, every time it is called, it should add the last digit in n to a new number, y. Thus, if n = 235, the while loop will iterate 3 times, and each time f() is called, it should add 5, 3, and 2, to the value y.

Upvotes: 7

Views: 11010

Answers (3)

faraz naeem
faraz naeem

Reputation: 121

Below is the code which has 11510 leetcode test cases and it is accepted check a number is palindrome without converting it into string

var isPalindrome = function(x) {
let list=[]
if(x<0){
    return false
}
while(x>0){
    if(x<10){
        list.push(parseInt(x))
        break;
    }
    let num=parseInt( x%10)
    list.push(num)
    x=parseInt( x/10)
}  
for(var i=0;i<list.length/2;i++){
    if(list[i]!=list[list.length-(i+1)]){
        return false
    }
}
return true

};

thanks,

Upvotes: 0

kennert
kennert

Reputation: 31

Excellent solution, mate! Maybe one little suggestion. Your solution iterates over all n digits, but you have only to iterate n/2 digits. Moreover, you can handle negative values directly because they aren't palindromes.

def is_palindrome(x):
    if x < 0 or (x % 10 == 0 and x != 0):
        return False
    head, tail = x, 0
    while head > tail:
        head, tail = head // 10, tail * 10 + head % 10
    # When the length is an odd number, we can get rid of the middle digit by tail // 10
    return head == tail or head == tail // 10

Time complexity: O(log(n)) because we divided 10 in every iteration
Space complexity: O(1)

Upvotes: 3

Taku
Taku

Reputation: 33744

Here's the logic: (y * 10) + x % 10

def is_palindrome(n):
    x, y = n, 0
    f = lambda: (y * 10) + x % 10
    while x > 0:
        x, y = x//10 , f()
    return y == n

print(is_palindrome(123454321))
# True
print(is_palindrome(12))
# False

y*10 moves the current y to the left by 1 digit, and x%10 adds the last digit. 

print(is_palindrome(235))
# False

Pre-iteration: x = 235, y = 0

First iteration: x = 23, y = 5

Second iteration: x = 2, y = 53

Third iteration: x = 0, y = 532

Upvotes: 16

Related Questions