Introduction
Checking whether a number is a palindrome can be a common problem in programming, and there are different approaches to solving it. In this article, we will discuss an algorithm for checking if a number is a palindrome number. We will explain the steps involved in the algorithm, provide examples to illustrate it, and explore its time and space complexity.
In this article, we will understand the general algorithm for checking palindrome numbers. But there are different approaches and special cases. If you want to learn more about this and see solutions in multiple programming languages. We will focus on Java implementation in this article.
What is Palindrome Number?
A palindrome number is a number that reads the same forward and backward. In other words, if you reverse the digits of a palindrome number, you get the same number.
For example, 121 is a palindrome number because if you read it backward, it is still 121.
Another example of a palindrome number is 132231. If you read 132231 backward, it is still 132231.
However, a number like 123 is not a palindrome number because if you read it backward, it becomes 321, which is not the same as the original number.
Palindrome numbers are interesting and useful in many areas, including mathematics, computer science, and cryptography.
Problem Statement
Given a positive integer number num, Print whether the number is a palindrome number or not.
Example 1:
Input: 1256521
Output: Yes, It is a palindrome number
Example 2:
Input: 12345421
Output: No, It is not a palindrome number
So before moving to see the solution, first give try on solving this problem on your own. You can practice it here.
Approach 1:
One approach to checking if a number is a palindrome is to reverse the digits of the number and compare it with the original number. If the reversed number is the same as the original number, then the number is a palindrome.
To understand this approach better, let’s take an example. Suppose we want to check if the number 12321 is a palindrome. We can reverse the digits of the number to get 12321. We can then compare this with the original number, which is also 12321. Since the reversed number is the same as the original number, we can conclude that 12321 is a palindrome number. So let’s see the working algorithm for this approach.
Algorithm
Suppose the input is given as a positive integer num.
- Initialize a new variable reverseNum to 0.
- Initialize a new variable temp to num
- While temp is not equal to 0:
- Calculate the remainder when the temp is divided by 10 and store it in a variable digit.
- Multiply reverseNum by 10 and add the digit to it.
- Divide temp by 10 and discard any remainder.
- If num is equal to reverseNum, return true. (num is a palindrome number)
- Otherwise, return false. (num is not a palindrome number)
Implementation
import java.util.Scanner;
public class Main {
public static void main(String args[]) {
Scanner input = new Scanner(System.in); // Getting the user input
int num = input.nextInt();
// Initialize variables
int reverseNum = 0;
int temp = num;
// Reverse the digits of the number
while (temp != 0) {
int digit = temp % 10;
reverseNum = reverseNum * 10 + digit;
temp = temp / 10;
}
// Check if the original number is equal to the reversed number
if (num == reverseNum) {
System.out.println(" Yes, "+ num +" is a palindrome number");
} else {
System.out.println(" No, "+ num +" is not a palindrome number.");
}
}
}Run this Code
Input: 123
Output: No, 123 is not a palindrome number.
Input: 12321
Output: Yes, 12321 is a palindrome number.
In the first approach, we used the method of reversing the number. However, this approach has a drawback, which is that it may not work for large input numbers that cannot fit in an integer or float data type. In such cases, the second approach can be used.
Approach 2:
We can take the input from the user in the form of a string or convert the number to a string format. With the help of two pointers pointing at the start and end of the string, we can iterate over the string and check whether it is a palindrome or not. The algorithm below explains the steps to solve this.
Algorithm:
- Convert “num” into a string “str”
Initialize two pointers “left” and “right” pointing to the start and end of “str”, respectively
While “left” is less than or equal to “right”, do the following:
If the characters at “left” and “right” are not equal, set “isPalindrome” to false and break the loop
Otherwise, increment “left” and decrement “right”
If the loop completes without breaking, set “isPalindrome” to true
Return “isPalindrome”
Code:
import java.util.Scanner;
public class PalindromeNumber {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter a number: ");
int num = sc.nextInt();
boolean isPalindrome = checkPalindrome(num);
if (isPalindrome) {
System.out.println(num + " is a palindrome number");
} else {
System.out.println(num + " is not a palindrome number");
}
sc.close();
}public static boolean checkPalindrome(int num) {
String str = Integer.toString(num);
int left = 0;
int right = str.length() - 1;
while (left <= right) {
if (str.charAt(left) != str.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
}Input: 123
Output: 123 is not a palindrome number.
Input: 12321
Output: 12321 is a palindrome number.Time Complexity: O(log n), where n is the input number. This is because we need to iterate over each digit of the input number, and the number of digits in the number is proportional to its logarithm base 10.
Space complexity: O(1), as we only use a constant amount of additional memory to store a few variables.
Conclusion
In conclusion, we have seen how to check if a number is a palindrome using two approaches in Java. The first approach involves reversing the digits of the number and checking if the original number is equal to the reversed number. The second approach involves comparing the first and last digits of the number, then iteratively checking the remaining digits. Both approaches have a time complexity of O(log n) and a space complexity of O(1), making them efficient and practical for checking large numbers.
