Palindrome Integer | InterviewBit | Solution Explained

Palindrome Integer is a very standard problem. I explain 2 solutions in both CPP and Python3. Problem Link.

0. Palindrome Integer: Problem Discussion

0.0. IO Format

  • input:
    • an integer in the standard range: -2^31 to 2^31-1
  • output:
    • 1 if the input is a palindromic number and 0 otherwise

Palindromic number: A number that can be read the same way forward and backward.

0.1. Examples

  • 123 is not a palindrome
  • 121 is a palindrome
  • 123321 is a palindrome
  • 12321 is a palindrome

1. Palindrome Integer: Complete Reversal Solution

Since the problem clearly mentions that we need to be able to read the solution both in forward and backward directions, won’t it be nice if we could reverse the digits of the number?

One way is to start a variable rev with 0 and each time, extract one digit from the right side of A. So, we extract digits from A’s end and add them at the end of rev. This is a good time to whip out your notebook and actually try it out!

int Solution::isPalindrome(int A) {
    if (A < 0) return 0;
    if (A < 10) return 1;

    long long rev = 0;
    int A_copy = A;
    while (A) {
        rev = rev * 10 + (A % 10);
        A /= 10;
    }

    if (A_copy == rev) return 1;
    else return 0;
}
class Solution:
    def isPalindrome(self, A):
        if A < 0: return 0
        if A < 10: return 1
        
        A_copy = A
        rev = 0
        while A:
            rev = rev*10 + A%10
            A //= 10
        
        return int(A_copy == rev)

2. Palindrome Integer: Half Reversal

There is a small catch with the above solution. Note how I used long long int instead of just int in the CPP solution. That’s because if we have a large number like 1,999,999,999, when we reverse the digits, we get 9,999,999,991. This is above the integer limit!

To bypass this problem, we can stop the extraction of digits midway. The below logic indicates.

class Solution:
    def isPalindrome(self, A):
        if A < 0: return 0
        if A < 10: return 1
        
        
        rev = 0
        while A > rev:
            rev = rev*10 + A % 10
            A //= 10
        
        if rev < 10:
            return int(rev == A)
        else:
            return int(rev == A or rev//10 == A)

Both work in O(1) time and space.

    Leave a Reply

    Your email address will not be published. Required fields are marked *