Given a number ‘n’ and our goal is to find out it is palindrome or not without using any extra space. We can’t make a new copy of number.
Examples:
Input: n = 2332 Output: Yes it is Palindrome. Explanation: original number = 2332 reversed number = 2332 Both are same hence the number is palindrome. Input: n=1111 Output: Yes it is Palindrome. Input: n = 1234 Output: No not Palindrome.
Other Approach: The other recursive approaches and the approach to compare the digits are discussed in Set-1 of this article. Here, we are discussing the other approaches.
Approach: This approach depends upon 3 major steps, find the number of digits in the number. Partition the number into 2 parts from the middle. Take care of the case when the length is odd, in which we will have to use the middle element twice. Check whether the number in both numbers are the same or not. Follow the steps below to solve the problem:
Below is the implementation of the above approach.
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find if the number is a // pallindrome or not bool isPalindrome(int n) { if (n < 0) return false; if (n < 10) return true; // Find the length of the number int K = ceil(log(n) / log(10)); int ans = 0; // Partition the number into 2 halves for (int i = 0; i < K / 2; i++) { ans = ans * 10 + n % 10; n = n / 10; } if (K % 2 == 1) ans = ans * 10 + n % 10; // Equality Condition return (ans == n); } // Driver Code int main() { isPalindrome(1001) ? cout << "Yes, it is Palindrome" : cout << "No, not Palindrome"; return 0; }
Output
Yes, it is Palindrome
Time Complexity: O(K), where K is the number of digits
Auxiliary Approach: O(1)