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("Truen");
}
else
{
// number is not palindrome
printf("Falsen");
}
}
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("Truen");
}
else
{
// number is not palindrome
printf("Falsen");
}
}
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.
