Check Whether a Number Is a Palindrome

114.3k
0

Given an integer n, check whether it is a palindrome number or not.

A palindrome number stays the same even after its digits are reversed.

Example 1

Input: n = 121

Output: true

Explanation: Reading 121 from both sides gives the same number.

Example 2

Input: n = 10

Output: false

Explanation: Reversing 10 gives 01, which is not the same as 10.

Brute Force Approach

A palindrome number follows the same pattern as a palindrome word. The digit at the beginning should match the digit at the end, then the next digit from the left should match the next digit from the right, and this checking keeps moving inward.

That observation naturally suggests converting the number into a string. Once the digits are available as characters, comparing the outer pairs becomes simple and direct.

A small edge case appears before that. Negative numbers are not palindrome numbers in the standard version of this problem, because the minus sign appears only on the left side and has no matching character on the right side.

Algorithm

  • First, check whether the number is negative. This is necessary because a minus sign breaks the mirror pattern, so the number cannot read the same from both directions.

  • Convert the number into a string. This helps access digits from both ends easily, without repeatedly extracting digits using division and modulo.

  • Keep one pointer at the start of the string and another at the end. These pointers mark the two digits that should match if the number is truly a palindrome.

  • Compare the digits at both pointers. If they are different, the answer should immediately become false because one mismatch is enough to prove the number is not a palindrome.

  • If the digits match, move the left pointer one step to the right and the right pointer one step to the left. This is done to continue checking the next inner pair.

  • Repeat this process until the pointers meet or cross. At that moment, every important pair has already been checked, so the number is a palindrome.

Dry Run

Check Palindrome Number Brute Dry Run

Check Palindrome Number Brute Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/*
Checks if the number is a palindrome using string comparison.
*/
bool isPalindrome(int n) {
// Negative numbers are not palindromes.
if (n < 0) {
return false;
}
// Convert number to string.
string s = to_string(n);
// Pointers for both ends.
int left = 0;
int right = (int)s.size() - 1;
// Compare digits from both sides.
while (left < right) {
// Mismatch means not a palindrome.
if (s[left] != s[right]) {
return false;
}
// Move to the next left digit.
left++;
// Move to the next right digit.
right--;
}
return true;
}
};
// Driver code starts
int main() {
Solution sol;
cout << (sol.isPalindrome(121) ? "true" : "false") << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(log10 n) because every digit is checked at most once.

Space Complexity: O(log10 n) because the number is stored as a string.

Better Approach

A number is a palindrome if it reads the same from left to right and right to left. Instead of converting the number into a string, we can mathematically reverse the digits and compare the reversed number with the original.

Algorithm

  • Store original = n. We need the original value after modifying n.

  • Initialize reverse = 0. This will store the reversed number.

  • While n > 0 perform the following operations:

    • Extract the last digit using n % 10.

    • Add it to reverse.

    • Remove the last digit using n /= 10 to process next numbers.

  • Compare reverse with original. Equality means the number is identical to its reverse.

  • Handle negative numbers separately, they cannot be a palindrome.

Dry Run

Check Palindrome Number Better Dry Run

Check Palindrome Number Better Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Checks whether a number is palindrome or not
bool isPalindrome(int n) {
// Negative numbers cannot be palindromes.
if (n < 0) return false;
// Store the original number because x will be modified.
int original = n;
// Store the reversed number.
long long rev = 0;
// Process every digit of the number.
while (n > 0) {
// Extract the last digit.
int digit = n % 10;
// Append the extracted digit to the reversed number.
rev = rev * 10 + digit;
// Remove the last digit from x.
n /= 10;
}
// A palindrome is equal to its reversed form.
return rev == original;
}
};
// Driver code
int main() {
Solution s;
cout << s.isPalindrome(121) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(log10 n) because the number of digits processed depends on the number of digits in the number.

Space Complexity: O(1) because only a few variables are used.

Optimal Approach

The key observation is that a palindrome matches from both ends.

So instead of reversing the full number, only the last half of the digits can be reversed and compared with the first half. Once the reversed half becomes greater than or equal to the remaining half, enough digits have already been processed.

This also explains two important edge cases quickly:

  • Any negative number is not a palindrome because of the minus sign.

  • Any number ending in 0 cannot be a palindrome unless the number itself is 0, because a palindrome cannot start with 0.

Algorithm

  • First, return false if the number is negative, because a minus sign breaks the palindrome pattern.

  • Return false if the number ends with 0 but is not 0, because a palindrome cannot start with 0.

  • Build the reversed second half of the number, because only half is enough for comparison.

  • In each step, take the last digit from the number and add it to the reversed half.

  • Remove that last digit from the original number so the remaining part acts like the first half.

  • Stop when the remaining number becomes smaller than or equal to the reversed half, because half the digits have already been checked.

  • Compare both halves. For odd-length numbers, ignore the middle digit by dividing the reversed half by 10.

Key Points

  • 0 is a palindrome.

  • Negative numbers are not treated as palindromes in the standard version of this problem.

  • For odd-length numbers like 121, the middle digit can be ignored during the final comparison.

Dry Run

Check Palindrome Number Optimal Dry Run

Check Palindrome Number Optimal Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/*
Checks whether the given integer is a palindrome without converting it to a string.
*/
bool isPalindrome(int n) {
// Negative numbers and numbers ending in 0 cannot be palindromes,
// except the number 0 itself.
if (n < 0 || (n % 10 == 0 && n != 0)) {
return false;
}
// This stores the reversed second half of the number.
int reversedHalf = 0;
while (n > reversedHalf) {
// Add the current last digit into the reversed half.
reversedHalf = reversedHalf * 10 + n % 10;
// Remove the current last digit from remaining first half.
n /= 10;
}
// For even digits, both halves must match.
// For odd digits, the middle digit is removed from reversedHalf.
return n == reversedHalf || n == reversedHalf / 10;
}
};
// Driver code starts
int main() {
int n = 121;
Solution obj;
cout << (obj.isPalindrome(n) ? "true" : "false") << "\n";
return 0;
}

Complexity Analysis

Time Complexity: O(log10 n) because the number of digits processed depends on the number of digits in the number.

Space Complexity: O(1) because only a few variables are used.

Interview follow-up Questions

Because of the minus sign. For example, -121 does not look the same when reversed.

MathsStringIntroduction to DSATwo PointerStack

Read Similar Blogs

String

Word Count

Count Words in a String Using String Traversal Problem Statement Write a program to count the number of words in a given string. A word is a continuous group of characters separated by one or more...

50.9k
String

Introduction (covers string introduction, vowels/consonants, character search, character frequency, first non-repeating character, reverse string, remove spaces, toggle case)

https://static.takeuforward.org/blogs/draft/chatgpt-image-jun-5-2026-10-58-35-am-05e285.webp tuf-image-slider-1 Given a string, the task is to understand how to visit ea...

97.3k
MathsIntroduction to DSA

Mastering Number Basics in Programming

Introduction Numbers are one of the first things that appear in DSA, and they are much friendlier than they look. A number can be checked, divided, broken into digits, counted, and compared. These...

73.6k
Comments0