LeetCode Palindrome Number

Problem statement

Given an integer x, return true if x is palindrome integer.

An integer is a palindrome when it reads the same backward as forward. For example, 121 is palindrome while 123 is not.

Example 1:

Input: x = 121
Output: true

Example 2:

Input: x = -121 
Output: false

Example 3:

Input: x = 10
Output: false

Example 4:

Input: x = -101 
Output: false

Constraints:

- -2^31 <= x <= 2^31 - 1

Explanation

As mentioned in the problem statement, palindrome number is one that reads the same from both sides.

Brute force solution

A brute force solution will be to convert the integer into a string, reverse the string, and check if the two strings are the same.

But this approach will require extra space for creating a string.

The time complexity of this program will be O(N). The space complexity will be O(M) where M is the number of digits in the integer.

Optimized solution

We can avoid the extra space and reduce the time complexity similar to the way we check palindrome string. But here, we get the first and last digits and compare them.

Fetching the last digit is simple and, we can use the modulus operator %. Fetching the first digit can be done using a divisor.

Let’s check the algorithm.

Algorithm

- if x < 0 
  - return false. 
- set divisor = 1 
// We use the divisor to compute the number of digits in the number x.
// We keep multiplying the divisor by 10 till x / divisor is greater than equal to 10. 
- Loop while x / divisor >= 10 
  - divisor = divisor * 10 
- Loop while x != 0 
  // here we check if first and last digit are same or not. 
  - if x / divisor != x % 10 
    - return false 
    // remove the first digit 
    - set x = x % divisor 
    
    // remove the last digit 
    - set x = x / 10 
   // since first and last digit are removed we divide divisor by 100 
    - set divisor = divisor / 100 
- return true

C++ solution

class Solution {
public: 
    bool isPalindrome(int x) {
        if(x < 0){
            return false;
        }
        int divisor = 1;
        while(x/divisor >= 10){
            divisor *= 10;
        }
        while(x != 0){
            if (x / divisor != x % 10) {
                return false;
            }
            x %= divisor;
            x /= 10;
            divisor /= 100;
        }
        return true;
    }
};

Golang solution

func isPalindrome(x int) bool {
    if x < 0 {
        return false
    }
    divisor := 1
   
    for x / divisor >= 10 {
        divisor *= 10
    }
    for x != 0 {
        if x / divisor != x % 10 {
            return false
        }
        x %= divisor
        x /= 10
        divisor /= 100
    }
    return true
}

Javascript solution

var isPalindrome = function(x) {
    if( x < 0 ){
        return false;
    }
    let divisor = 1;
    while( x / divisor >= 10 ){
        divisor *= 10;
    }
    while( x != 0 ){
        if( Math.trunc(x / divisor) != Math.floor(x % 10) ){
            return false;
        }
        x %= divisor;
        x = Math.floor( x / 10 );
        divisor /= 100;
    }
    return true;
};

Let’s dry-run our algorithm.

x = 12321 
Step 1: x < 0 
        12321 < 0 
        false 
Step 2: divisor = 1 
Step 3: while x / divisor >= 10
 
        1. 12321 / 1 >= 10 
           12321 >= 10 
           divisor *= 10 
           divisor = 10 
        2. 12321 / 10 >= 10 
           1232 >= 10 
           divisor *= 10 
           divisor = 100 
        3. 12321 / 100 >= 10 
           123 >= 10 
           divisor *= 10 
           divisor = 1000 
        4. 12321 / 1000 >= 10 
           12 >= 10 
           divisor *= 10 
           divisor = 10000 
        5. 12321 / 10000 >= 10 
           1 >= 10 
           Loop exit 
Step 4: while x != 0 
        
        1. 12321 / 10000 != 12321 % 10 
           1 != 1 
           false 
 
           x %= divisor 
           x = 12321 % 10000 
           x = 2321 
           x /= 10 
           x = 232 
           divisor /= 100 
           divisor = 100 
        2. 232 / 100 != 232 % 10 
           2 != 2 
           false 
           x %= divisor 
           x = 232 % 100 
           x = 32 
           x /= 10 
           x = 3 
           divisor /= 100 
           divisor = 1 
        3. 3 / 1 != 3 % 10 
           3 != 3 
           false 
           x %= divisor 
           x = 3 % 1 
           x = 0 
           x /= 10 
           x = 0 
           divisor /= 100 
           divisor = 0 
        4. x != 0 
           0 != 0 
           Loop exit 
Step 5: return true

Originally published at https://alkeshghorpade.me.