Competitive Programming, Problems, Programming Questions

Palindrome Number – LeetCode Problem

10 min read
Palindrome Number

Hi there, fellow geeks! In this article, we will look at some numbers and try to work out some algorithms to deduce whether the given number is a palindrome or not. Please note that for the scope of our discussion, palindrome and palindrome number means the same thing.

A palindrome number is a word or phrase that reads the same backwards as it reads forward. For example, tenet is a palindrome word, 1234321 is a palindrome number and so on.

Fig.: Palindrome numbers

Link to the LeetCode Problem : Click Here

The problem statement says that we are given an integer number as input and our job is to write a function that returns Boolean value true if a number is a palindrome, and false otherwise. Keep in mind that, a negative number, an imaginary number and a decimal number can never be a palindrome number.

Approach 1 (Brute Force):

The most basic approach is to check whether the first digit is equal to the last digit, the second digit is equal to the second last digit and go on checking until we reach the middlemost digit. To check this, we create an array data structure of size equal to the number of digits in the number. Then we need to put all the digits of the input number into the array and iterate each node, meanwhile checking the above mentioned condition.

Algorithm :

Count the number of digits in num likewise,
i. Store num in x
ii. Set count = 0
iii. Repeat steps iv and v while x is not equal to 0
iv. count++
v. x = x/10
vi. Thus number of digits = count
Declare an array ‘arr’ of size equal to count
Repeat steps 4 and 5 while num is not equal to 0
Insert num%10 into the array
num = num/10
Set i = 0
Repeat step 8 until i is less than count/2
If arr[i] ≠ arr[count-i-1], then return false
Return true

Implementation in C :

// C program to check palindrome number
#include <stdio.h>
// function to count and return number of digits
int digits(int num)
{
    int count = 0;
    while (num != 0)
    {
        count++;
        num /= 10;
    }
    return count;
}
// function to check palindrome
// returns 1 if the number is a palindrome, 0 otherwise
int isPalindrome(int n)
{
    // negative numbers cannot be palindromes
    if (n < 0)
        return 0;
    // single digit numbers are always palindromes
    if (n < 10)
        return 1;
    // number of digits in the number
    int s = digits(n);
    // array to store the digits of n
    int digitArray[s];
    for (int i = 0; i < s; i++)
    {
        int temp = n % 10;
        n /= 10;
        // insert last digit into the array
        digitArray[s - i - 1] = temp;
    }
    for (int i = 0; i < s / 2; i++)
    {
        // if number is not palindrome then this block executes
        if (digitArray[i] != digitArray[s - i - 1])
            return 0;
    }
    // if all digits matched then the number is a palindrome
    return 1;
}
// driver function
int main()
{
    // given integer
    int n;
    scanf("%d", &n);
    // function call
    int flag = isPalindrome(n);
    if (flag == 1)
    {
        // number is palindrome
        printf("True\n");
    }
    else
    {
        // number is not palindrome
        printf("False\n");
    }
}

 

Implementation in C++ :

// C++ program to check palindrome number
#include <bits/stdc++.h>
using namespace std;
// class to encapsulate the solution
class Solution
{
public:
    // function to check palindrome
    // returns true if the number is a palindrome, false otherwise
    bool isPalindrome(int n)
    {
        // negative numbers cannot be palindromes
        if (n < 0)
            return false;
        // single digit numbers are always palindromes
        if (n < 10)
            return true;
        // vector to store the digits of n
        vector<int> digits;
        while (n)
        {
            int temp = n % 10;
            n /= 10;
            // insert last digit into the vector
            digits.push_back(temp);
        }
        int s = digits.size();
        for (int i = 0; i < s / 2; i++)
        {
            // if number is not palindrome then this block executes
            if (digits[i] != digits[s - i - 1])
                return false;
        }
        // if all digits matched then the number is a palindrome
        return true;
    }
};
// driver function
int main()
{
    // given number
    int num;
    cin >> num;
    // object of class Solution
    Solution obj;
    bool what = obj.isPalindrome(num);
    // ternary operator to reduce lines of code
    cout << (what ? "True" : "False") << endl;
    return 0;
}

 

Implementation in Java :

//Java program to check palindrome number
import java.util.Scanner;
//class to encapsulate the solution
class Solution {
    // function to return number of digits in a number
    public int digitCount(int n) {
        int N = n;
        int count = 0;
        while (N != 0) {
            count++;
            N /= 10;
        }
        return count;
    }
    // function to check palindrome
    // returns true if palindrome found, false otherwise
    public boolean isPalindrome(int n) {
        // negative numbers can never be palindromes
        if (n < 0)
            return false;
        // single digit numbers are always palindromes
        if (n < 10)
            return true;
        int N = n;
        int s = digitCount(n);
        // array to store digits
        int arr[] = new int[s];
        int i = s;
        // while loop to insert digits into array
        while (N != 0) {
            i--;
            int temp = N % 10;
            arr[i] = temp;
            N /= 10;
        }
        // for loop to check if corresponding digits are equal
        for (int j = 0; j < s / 2; j++) {
            // this block executes if number is not palindrome
            if (arr[j] != arr[s - j - 1])
                return false;
        }
        // if for loop completes, number is a palindrome
        return true;
    }
}
// driver class
class pal_num1 {
    public static void main(String args[]) {
        // Scanner class object to take user input
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        // object of class Solution
        Solution obj = new Solution();
        // function call
        boolean flag = obj.isPalindrome(n);
        if (flag == true) {
            // if number is palindrome
            System.out.println("True");
        } else {
            // if number is not palindrome
            System.out.println("False");
        }
        // closing Scanner class object
        scan.close();
    }
}

 

Implementation in Python :

#Python program to check palindrome
#function to return number of digits
def digits(n):
    x = n
    count = 0
    #while loop to count digits
    while (x != 0):
        count = count + 1
        x = x / 10
        x = int(x)
    return count
#.....................................#
#function to check palindrome
#returns true if palindrome found, else false
def isPalindrome(n):
    x = n
    #list to store digits
    mylist = []
    while (x != 0):
        mylist.append(x % 10)
        x /= 10
        x = int(x)
    #size of mylist
    s = digits(n)
    for i in range(0, s):
        #this block executes when number is not palindrome
        if (mylist[i] != mylist[s - i - 1]):
            return False
    return True
#........................................#
#driver code
n = input()
n = int(n)
#function call
flag = isPalindrome(n)
if (flag):
    #if number is palindrome
    print("True")
else:
    #if number is not palindrome
    print("False")

 

Analysis of the Algorithm :

This algorithm consumes a time complexity of O(n) and space complexity of O(n). Here ‘n’ is the number of digits in the given integer. The time complexity is observed because we iterate through an array of size ‘n’. The space complexity is also because of the same array.

Approach 2 (Reversal of the Number):

Another method to solve the problem is by reversing the given integer. We will reverse the digits of the original number and compare them. If the original number and the new number turn out to be same, then we can conclude that the given integer is a palindrome number. We achieve this by repeatedly multiplying the last digit of the given integer by 10 (using the modulo operator to find the remainder), and then dividing the integer by 10. This step is repeated till the given integer becomes zero. An algorithm for this process is given below.

Algorithm :

If num is negative return false
Store num into x
Set rev = 0
Repeat steps 5 and 6 until x becomes 0
rev = rev*10 + x%10
x = x/10
If rev = num, return true
Return false

Implementation in C :

// C program to check palindrome number
#include <stdio.h>
// function to check palindrome
// returns 1 if the number is a palindrome, 0 otherwise
int isPalindrome(int n)
{
  if (n < 0)
    return 0;
  long long int N = n;
  long long int rev = 0;
 
 
  // while loop to reverse the digits
  while (N != 0)
  {
    rev = rev * 10 + (N % 10);
    N /= 10;
  }
  // returns true if the numbers are equal and false otherwise
  return (rev == n);
}
// driver function
int main()
{
  // given integer
  int n;
  scanf("%d", &n);
  // function call
  int flag = isPalindrome(n);
  if (flag == 1)
  {
    // number is palindrome
    printf("True\n");
  }
  else
  {
    // number is not palindrome
    printf("False\n");
  }
}

 

Implementation in C++ :

// C++ program to check palindrome number
#include <bits/stdc++.h>
using namespace std;
// class to encapsulate the solution
class Solution
{
public:
  // function to check palindrome
  // returns true if the number is a palindrome, false otherwise
  bool isPalindrome(int n)
  {
    if (n < 0)
      return false;
    long long int N = n;
    long long int rev = 0;
    // while loop to reverse the digits
    while (N != 0)
    {
      rev = rev * 10 + (N % 10);
      N /= 10;
    }
    // returns true if the reversed number is equal to the original number
    return (rev == n);
  }
};
// driver function
int main()
{
  // given number
  int num;
  cin >> num;
  // object of class Solution
  Solution obj;
  bool what = obj.isPalindrome(num);
  // ternary operator to reduce lines of code
  cout << (what ? "True" : "False") << endl;
  return 0;
}

 

You can try out the codes in our very own IDE https://ide.codewithgeeks.com/.

 

Implementation in Java:

//Java program to check palindrome
import java.util.Scanner;
//class to encapsulate the solution
class Solution {
  // function to check palindrome
  // returns true if palindrome found, false otherwise
  public boolean isPalindrome(int n) {
    // negative numbers can never be palindromes
    if (n < 0)
      return false;
    // single digit numbers are always palindromes
    if (n < 10)
      return true;
    int N = n;
    int rev = 0;
    // while loop to reverse digits
    while (N != 0) {
      rev = rev * 10 + (N % 10);
      N /= 10;
    }
    // returns true if reversed number is equal to original number
    return (n == rev);
  }
}
// driver class
class pal_num2 {
  public static void main(String args[]) {
    // Scanner object to take user input
    Scanner scan = new Scanner(System.in);
    // object of class Solution
    Solution obj = new Solution();
    int n = scan.nextInt();
    // function call
    boolean flag = obj.isPalindrome(n);
    if (flag == true) {
      // if number is a palindrome
      System.out.println("True");
    } else {
      // if number is not a palindrome
      System.out.println("False");
    }
    // closing the object of Scanner class after use
    scan.close();
  }
}

 


Implementation in Python:

#Python program to check palindrome
#function to check palindrome
#returns true if palindrome found, else false
def isPalindrome(n):
  rev = 0
  x = n
  #while loop to reverse digits
  while (x != 0):
    rev = rev * 10 + x % 10
    x = x / 10
    x = int(x)
  #returns true if both are equal
  return (rev == n)
#.........................................#
#driver code
n = input()
n = int(n)
#function call
flag = isPalindrome(n)
if (flag):
  #if number is palindrome
  print("True")
else:
  #if number is not palindrome
  print("False")

 

Analysis of the Algorithm:

You can obviously tell that this algorithm is much better than the previous one. Although it also runs in a time complexity of O(n), we will iterate ‘n’ elements only once in this method. Whereas in the previous method we had to iterate twice: 1. While creating the array, 2. While checking the opposite facing numbers. More importantly, this algorithm uses a space complexity of O(1), because we are using no extra containers, like array, for solving the problem. Besides, this algorithm requires less lines of code and it is also cleaner than the previous one.

Conclusion:

Thus, it can be concluded that to check if an integer is a palindrome number, the best method is to reverse the given integer and compare it with the original number to check if it matches. If they are same then the given number is a palindrome number, else not.

Frequently Asked Questions:

Q1. How do you find a palindrome in a word?

Ans. We can either check each letter with its corresponding letter from the back, or we can reverse the letters of the word.

Q2. What is a palindrome?

Ans. A palindrome is a word or number or sentence that reads the same starting from both front and back.

Q3. How many words are there that are palindromes?

Ans. There might be a large number of words that are palindromes. However, it would take some research to find them.

Q4. Is 7 a palindrome number?

Ans. Yes. In fact, all single digit numbers are palindrome numbers.

 

 

 


Leave a Reply

Your email address will not be published.

Sign up for our Newsletter

Get all the latest updates on what’s happening in the tech & startup world, delivered straight to your inbox from us.