Given an integer n, determine whether it reads the same from left to right and right to left using recursion.
Return true if the number is a palindrome. Otherwise, return false.
Under the usual integer-palindrome convention, negative numbers are not considered palindromes.
Example 1
Input: n = 121
Output: true
Explanation: Reading 121 from left to right gives the exact same sequence as reading it from right to left.
Example 2
Input: n = -121
Output: false
Explanation: Reading from left to right is -121. From right to left, it becomes 121-. Since the negative sign moves to the back, it is not a palindrome.
Approach 1
A number is a palindrome when reversing its digits gives back the same number.
For example, reversing 121 still gives 121.
To reverse a number recursively, we can take its last digit using % 10 and add that digit to a running reversed value. Multiplying the reversed value by 10 first shifts its existing digits one place to the left, leaving room for the new digit.
At the same time, dividing the original number by 10 removes the digit we just processed. Repeating this eventually reduces the number to 0, at which point the reversed number is ready to compare with the original.
Algorithm
For a negative input, return
false, since negative numbers are not treated as palindromes in this problem.Use a recursive helper with the current number and
reversedNumber. The second parameter keeps track of the reversed value built from the digits processed so far.When the current number becomes
0, returnreversedNumber, because there are no more digits left to process.Extract the last digit using
n % 10. Add it to the reversed value usingreversedNumber × 10 + digit, which places the digit at the end of the reversed number.Continue recursively with
n / 10and the updated reversed value. Once the helper returns, compare the reversed number with the original input.
Dry Run
Check if palindrome mathematical reversal using recursion dry run .png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: // Builds the reversed number // using recursive digit processing. long long reverseDigits( int n, long long reversedNumber ) { // No digits remain // to be processed. if (n == 0) { return reversedNumber; } int digit = n % 10; // Add the current last digit // to the reversed number. reversedNumber = reversedNumber * 10 + digit; // Remove the processed digit // and continue recursively. return reverseDigits( n / 10, reversedNumber ); }public: // Checks whether the number // reads the same after reversal. bool isPalindrome(int n) { // Negative numbers are // not considered palindromes. if (n < 0) { return false; } long long reversedNumber = reverseDigits(n, 0); return reversedNumber == n; }};int main() { int n = 121; Solution solution; cout << ( solution.isPalindrome(n) ? "true" : "false" ) << endl; return 0;}Complexity Analysis
Time Complexity: O(D), where D is the number of digits. One digit is removed in every recursive call. Since D = O(log₁₀ N), this can also be written as O(log N).
Space Complexity: O(D), because one call-stack frame is used for each digit.
Approach 2
Another way to check whether a number is a palindrome is to compare corresponding digits from both ends.
Convert the number into a string and use two pointers: left at the beginning and right at the end. For the number to be a palindrome, the characters at these positions must match.
If a mismatch is found, the number cannot be a palindrome, so the recursion can stop immediately. Otherwise, move both pointers inward and continue checking the remaining pair.
When the pointers meet or cross, every required pair has matched, confirming that the number is a palindrome.
This approach does not construct a reversed integer, so it also avoids the possibility of integer overflow while reversing the number.
Algorithm
If the input number is negative, return
false, since the negative sign prevents it from satisfying the required palindrome representation.Convert the non-negative number into a string so that its digits can be accessed directly from both ends.
Use a recursive helper with
leftandrightpointers, where they represent the current pair of digits being compared.If
left >= right, returntrue, because all required outer pairs have already matched.If the characters at
leftandrightare different, returnfalseimmediately, since a single mismatched pair is enough to prove that the number is not a palindrome.If both characters match, continue recursively with
left + 1andright - 1to check the next inner pair.
Dry Run
Check if palindrome string based two pointer recursion dry run .png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: // Compares matching characters // from both ends recursively. bool checkPalindrome( const string& number, int left, int right ) { // All required pairs // have already matched. if (left >= right) { return true; } // One mismatch proves // the number is not palindrome. if (number[left] != number[right]) { return false; } // Move inward to check // the next matching pair. return checkPalindrome( number, left + 1, right - 1 ); }public: // Checks palindrome using // recursive two-pointer comparison. bool isPalindrome(int n) { // Negative numbers are // not considered palindromes. if (n < 0) { return false; } string number = to_string(n); return checkPalindrome( number, 0, number.size() - 1 ); }};int main() { int n = 1221; Solution solution; cout << ( solution.isPalindrome(n) ? "true" : "false" ) << endl; return 0;}Complexity Analysis
Time Complexity: O(D), where D is the number of digits. Converting the number to a string takes O(D) time, and the recursive comparison checks at most D / 2 pairs.
Space Complexity: O(D), because the string representation requires O(D) space and the recursive call stack can also use up to O(D) space.
FAQs
Q1. Why use a string-based approach instead of reversing the number mathematically?
The string approach allows corresponding digits to be compared directly from both ends and avoids constructing a reversed integer. However, some interview problems may restrict string conversion specifically to test mathematical manipulation of digits.
Q2. Can reversing the number cause integer overflow?
Yes. If the reversed value exceeds the range supported by the chosen integer type, integer overflow can occur. Using a wider numeric type can reduce this risk, while the string-based approach avoids numeric reversal entirely.
Q3. Why does the recursion stop when left >= right?
At that point, every required pair of digits has already been compared. Reaching the middle without finding a mismatch confirms that the number is a palindrome.
Q4. Why are negative numbers considered non-palindromes?
Under the standard definition used in this problem, the negative sign appears only at the beginning, so the representation cannot read the same from both directions.
Q5. How many recursive calls are required?
At most about d / 2 recursive calls are needed because each call checks one pair and moves both pointers toward the center.
Q6. Can the same recursive technique be used directly on strings?
Yes. The same two-pointer recursion works for any string by comparing characters from both ends and moving inward after every successful match.
Be the first to add a comment.