Problem Statement: Given a number check if it is a palindrome.
An integer is considered a palindrome when it reads the same backward as forward.
Examples:
Example 1: Input: N = 123 Output: Not Palindrome Number Explanation: 123 read backwards is 321.Since these are two different numbers 123 is not a palindrome. Example 2: Input: N = 121 Output: Palindrome Number Explanation: 121 read backwards as 121.Since these are two same numbers 121 is a palindrome.
Solution
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Approach: We can reverse the original number and compare the original with the reversed number. If both are the same, the number qualifies as a palindrome number.
Say the input number is X. Declare a variable Y to store the reverse and initialize it to 0. Make a copy of X, say dummy that will be used later for comparison.
Let’s understand the procedure to reverse a number.
- At every step extract the last digit using % operator. Suppose X%10 = d.
- We will append this last digit , d to Y using a formula 10*Y+d.
- The last digit of X has been used.Discard it using X/10.
Repeat these steps for the remaining digits. After every iteration, the size of X will shrink by one digit. Terminate the iteration when X = 0 meaning no new digits are left to be reversed.
The reversed number Y is compared with the dummy variable since X was destroyed while iteration. If Y equals dummy print “Palindrome Number” otherwise “Not Palindrome Number”.
Code:
C++ Code
#include <iostream>
using namespace std;
int reverse(int X) {
int Y = 0;
while (X > 0) {
//Extract the last digit
int digit = X % 10;
//Appending last digit
Y = Y * 10 + digit;
// Shrinking X by discarding the last digit
X = X / 10;
}
return Y;
}
int main() {
int X = 121;
int dummy = X;
int Y = reverse(X);
if (dummy == Y) {
cout << "Palindrome Number" << endl;
} else {
cout << "Not Palindrome Number" << endl;
}
return 0;
}
Output: Palindrome Number
Time Complexity: O(logN) for reversing N digits of input integer.
Space Complexity: O(1)
Java Code
public class Main {
static int reverse(int X) {
int Y = 0;
while (X > 0) {
//Extract the last digit
int digit = X % 10;
//Appending last digit
Y = Y * 10 + digit;
// Shrinking X by discarding the last digit
X = X / 10;
}
return Y;
}
public static void main(String[] args) {
int X = 121;
int dummy = X;
int Y = reverse(X);
if (dummy == Y) {
System.out.println("Palindrome Number");
}
else {
System.out.println("Not Palindrome Number");
}
}
}
Output: Palindrome Number
Time Complexity: O(logN) for reversing N digits of input integer.
Space Complexity: O(1)
Special thanks to Somparna Chakrabarti for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article