Home
Algorithms to Determine a Palindrome Number
Tags:, , , , , , ,

Algorithms to Determine a Palindrome Number

January 19, 2020 No Comments algorithms, c / c++, java, javascript, python, string

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Example 1:
Input: 121
Output: true

Example 2:
Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:
Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

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

Hints:
Beware of overflow when you reverse the integer.

Determine a Palindrome Number by Converting to String

Converting the number to string should be the fairly easiest approach. And there is no risks to overflow the integer when converting to a string. After converting to string, we can reverse the string and if the original number is a palindrome, the reversed version (string) should be exactly the same.

C++:

1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
    bool isPalindrome(int x) {
        string s = std::to_string(x);
        // we can also do the following
        // string r = s;
        // std::reverse(begin(r), end(r));
        string r(rbegin(s), rend(s)); 
        return r == s;
    }
};
class Solution {
public:
    bool isPalindrome(int x) {
        string s = std::to_string(x);
        // we can also do the following
        // string r = s;
        // std::reverse(begin(r), end(r));
        string r(rbegin(s), rend(s)); 
        return r == s;
    }
};

Java – we can use the StringBuilder’s method reverse() to reverse the string buffer:

1
2
3
4
5
6
7

class Solution {
    public boolean isPalindrome(int x) {
        String s = String.valueOf(x);
        String r = new StringBuilder(s).reverse().toString();
        return s.equals(r);
    }
}
class Solution {
    public boolean isPalindrome(int x) {
        String s = String.valueOf(x);
        String r = new StringBuilder(s).reverse().toString();
        return s.equals(r);
    }
}

Javascript: we convert the number x to string using new String() then, we split into array, reverse it, and join as a reversed string.

1
2
3
4
5
6
7
8

/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
    const r = (new String(x)).split("").reverse().join("");
    return r == x;
};
/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
    const r = (new String(x)).split("").reverse().join("");
    return r == x;
};

Python: We can reverse a string in a few ways: [::-1] is the Pythonic way.

1
2
3
4
5

class Solution:
    def isPalindrome(self, x: int) -> bool:
        s = str(x)
        r = s[::-1]
        return s == r
class Solution:
    def isPalindrome(self, x: int) -> bool:
        s = str(x)
        r = s[::-1]
        return s == r

Of course, we can compare the characters at both ends in a classic way.

C++:

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    bool isPalindrome(int x) {
        string s = std::to_string(x);
        for (int i = 0; i < s.size() / 2; ++ i) {
            if (s[i] != s[s.size() - 1 - i]) {
                return false;
            }
        }
        return true;
    }
};
class Solution {
public:
    bool isPalindrome(int x) {
        string s = std::to_string(x);
        for (int i = 0; i < s.size() / 2; ++ i) {
            if (s[i] != s[s.size() - 1 - i]) {
                return false;
            }
        }
        return true;
    }
};

Java:

1
2
3
4
5
6
7
8
9
10
11

class Solution {
    public boolean isPalindrome(int x) {
        String s = String.valueOf(x);
        for (int i = 0; i < s.length(); ++ i) {
            if (s.charAt(i) != s.charAt(s.length() - i - 1)) {
                return false;
            }
        }
        return true;
    }
}
class Solution {
    public boolean isPalindrome(int x) {
        String s = String.valueOf(x);
        for (int i = 0; i < s.length(); ++ i) {
            if (s.charAt(i) != s.charAt(s.length() - i - 1)) {
                return false;
            }
        }
        return true;
    }
}

Javascript:

1
2
3
4
5
6
7
8
9
10
11
12
13

/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
    const r = x + "";
    for (let i = 0; i < r.length; ++ i) {
        if (r[i] != r[r.length - 1 - i]) {
            return false;
        }
    }
    return true;    
};
/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
    const r = x + "";
    for (let i = 0; i < r.length; ++ i) {
        if (r[i] != r[r.length - 1 - i]) {
            return false;
        }
    }
    return true;    
};

Python:

1
2
3
4
5
6
7

class Solution:
    def isPalindrome(self, x: int) -> bool:
        s = str(x)
        for i in range(len(s) // 2):
            if s[i] != s[len(s) - i - 1]:
                return False
        return True
class Solution:
    def isPalindrome(self, x: int) -> bool:
        s = str(x)
        for i in range(len(s) // 2):
            if s[i] != s[len(s) - i - 1]:
                return False
        return True

Converting to strings require O(logN) space, and O(logN) time.

Determining the Palindrome Number by Extracting the Digits

We can repeatedly extract the right-most digit (least significant) and construct the reversed integer. However, we need to pay attention not to overflow the integer.

All negative numbers are not palindromes.

C++:

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) return false;
        int64_t s = x, r = 0;
        while (s > 0) {
            r = r * 10 + s % 10;
            s /= 10;
        }
        return x == r;
    }
};
class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) return false;
        int64_t s = x, r = 0;
        while (s > 0) {
            r = r * 10 + s % 10;
            s /= 10;
        }
        return x == r;
    }
};

Java:

1
2
3
4
5
6
7
8
9
10
11

class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0) return false;
        long s = x, r = 0;
        while (s > 0) {
            r = r * 10 + s % 10;
            s /= 10;
        }
        return x == r;
    }
}
class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0) return false;
        long s = x, r = 0;
        while (s > 0) {
            r = r * 10 + s % 10;
            s /= 10;
        }
        return x == r;
    }
}

Javascript: We need to use Math.floor to discard the fraction part for the integer division.

1
2
3
4
5
6
7
8
9
10
11
12
13

/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
    if (x < 0) return false;
    let s = x, r = 0;
    while (s > 0) {
        r = r * 10 + s % 10;
        s = Math.floor(s / 10);
    }
    return x === r;
};
/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
    if (x < 0) return false;
    let s = x, r = 0;
    while (s > 0) {
        r = r * 10 + s % 10;
        s = Math.floor(s / 10);
    }
    return x === r;
};

Python: beware we need to use // to do the integer division.

1
2
3
4
5
6
7
8
9
10

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0:
            return False
        r = 0
        s = x
        while s > 0:
            r = r * 10 + s % 10
            s //= 10
        return x == r
class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0:
            return False
        r = 0
        s = x
        while s > 0:
            r = r * 10 + s % 10
            s //= 10
        return x == r

Repeatedly extracting digits cost O(logN) time but the space usage is constant.

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
828 words
Last Post: Algorithm to Compute the Fraction to Recurring Decimal of the Two Integer Division
Next Post: Recursive Depth First Search Algorithm to Delete Leaves With a Given Value in a Binary Tree

The Permanent URL is: Algorithms to Determine a Palindrome Number

Related posts:

  1. How to Make a Safe Online Community for Your Business? When a person is passionate about something, they will want to seek out people with...
  2. Interview Question: The Number of Bits Required to Convert One Integer to Another (C/C++ function) The question is: how many bits are required to change if we want to convert...
  3. SQL Coding Exercise – Find Department Highest Salary Submit your solution: https://leetcode.com/problems/department-highest-salary/ As seen, two tables, you are asked to list the highest...
  4. Recursive Depth First Search Algorithm to Compute the Sum of Nodes with Even-Valued Grandparent in a Binary Tree Given a binary tree, return the sum of values of nodes with even-valued grandparent. (A...
  5. You need a Numeric Keypad to Start with Your HHKB! Getting a HHKB and being excited for a few days? Sooner or later, you ‘ll...
  6. How to Reverse Vowels of a String in C/C++? Write a function to reverse only the vowels of a string. Example: Given s =...
  7. Pointer Arithmetic in Delphi Delphi is based on Object Pascal, which is a great programming language. Delphi is also...
  8. Teaching Kids Programming – Number of Common Factors (Brute Force Algorithm + Greatest Common Divisor) Teaching Kids Programming: Videos on Data Structures and Algorithms Given two positive integers a and...

Leave a Reply