How do I check if a number is a palindrome?
Any language. Any algorithm. (except the algorithm of making the number a string and then reversing the string).
52 Answers
For any given number:
n = num;
rev = 0;
while (num > 0)
{
dig = num % 10;
rev = rev * 10 + dig;
num = num / 10;
}
If n == rev then num is a palindrome:
cout << "Number " << (n == rev ? "IS" : "IS NOT") << " a palindrome" << endl;
This is one of the Project Euler problems. When I solved it in Haskell I did exactly what you suggest, convert the number to a String. It's then trivial to check that the string is a pallindrome. If it performs well enough, then why bother making it more complex? Being a pallindrome is a lexical property rather than a mathematical one.
def ReverseNumber(n, partial=0):
if n == 0:
return partial
return ReverseNumber(n // 10, partial * 10 + n % 10)
trial = 123454321
if ReverseNumber(trial) == trial:
print("It's a Palindrome!")
Works for integers only. It's unclear from the problem statement if floating point numbers or leading zeros need to be considered.
int is_palindrome(unsigned long orig)
{
unsigned long reversed = 0, n = orig;
while (n > 0)
{
reversed = reversed * 10 + n % 10;
n /= 10;
}
return orig == reversed;
}
Push each individual digit onto a stack, then pop them off. If it's the same forwards and back, it's a palindrome.
Just for fun, this one also works.
a = num;
b = 0;
if (a % 10 == 0)
return a == 0;
do {
b = 10 * b + a % 10;
if (a == b)
return true;
a = a / 10;
} while (a > b);
return a == b;
I answered the Euler problem using a very brute-forcy way. Naturally, there was a much smarter algorithm at display when I got to the new unlocked associated forum thread. Namely, a member who went by the handle Begoner had such a novel approach, that I decided to reimplement my solution using his algorithm. His version was in Python (using nested loops) and I reimplemented it in Clojure (using a single loop/recur).
Here for your amusement:
(defn palindrome? [n]
(let [len (count n)]
(and
(= (first n) (last n))
(or (>= 1 (count n))
(palindrome? (. n (substring 1 (dec len))))))))
(defn begoners-palindrome []
(loop [mx 0
mxI 0
mxJ 0
i 999
j 990]
(if (> i 100)
(let [product (* i j)]
(if (and (> product mx) (palindrome? (str product)))
(recur product i j
(if (> j 100) i (dec i))
(if (> j 100) (- j 11) 990))
(recur mx mxI mxJ
(if (> j 100) i (dec i))
(if (> j 100) (- j 11) 990))))
mx)))
(time (prn (begoners-palindrome)))
There were Common Lisp answers as well, but they were ungrokable to me.
Here is an Scheme version that constructs a function that will work against any base. It has a redundancy check: return false quickly if the number is a multiple of the base (ends in 0).
And it doesn't rebuild the entire reversed number, only half.
That's all we need.
(define make-palindrome-tester
(lambda (base)
(lambda (n)
(cond
((= 0 (modulo n base)) #f)
(else
(letrec
((Q (lambda (h t)
(cond
((< h t) #f)
((= h t) #t)
(else
(let*
((h2 (quotient h base))
(m (- h (* h2 base))))
(cond
((= h2 t) #t)
(else
(Q h2 (+ (* base t) m))))))))))
(Q n 0)))))))
Pop off the first and last digits and compare them until you run out. There may be a digit left, or not, but either way, if all the popped off digits match, it is a palindrome.
Recursive way, not very efficient, just provide an option
(Python code)
def isPalindrome(num):
size = len(str(num))
demoninator = 10**(size-1)
return isPalindromeHelper(num, size, demoninator)
def isPalindromeHelper(num, size, demoninator):
"""wrapper function, used in recursive"""
if size <=1:
return True
else:
if num/demoninator != num%10:
return False
# shrink the size, num and denominator
num %= demoninator
num /= 10
size -= 2
demoninator /=100
return isPalindromeHelper(num, size, demoninator)
Assuming the leading zeros are ignored. Following is an implementation:
#include<bits/stdc++.h>
using namespace std;
vector<int>digits;
stack<int>digitsRev;
int d,number;
bool isPal=1;//initially assuming the number is palindrome
int main()
{
cin>>number;
if(number<10)//if it is a single digit number than it is palindrome
{
cout<<"PALINDROME"<<endl;
return 0;
}
//if the number is greater than or equal to 10
while(1)
{
d=number%10;//taking each digit
number=number/10;
//vector and stack will pick the digits
//in reverse order to each other
digits.push_back(d);
digitsRev.push(d);
if(number==0)break;
}
int index=0;
while(!digitsRev.empty())
{
//Checking each element of the vector and the stack
//to see if there is any inequality.
//And which is equivalent to check each digit of the main
//number from both sides
if(digitsRev.top()!=digits[index++])
{
cout<<"NOT PALINDROME"<<endl;
isPal=0;
break;
}
digitsRev.pop();
}
//If the digits are equal from both sides than the number is palindrome
if(isPal==1)cout<<"PALINDROME"<<endl;
}
Check this solution in java :
private static boolean ispalidrome(long n) {
return getrev(n, 0L) == n;
}
private static long getrev(long n, long initvalue) {
if (n <= 0) {
return initvalue;
}
initvalue = (initvalue * 10) + (n % 10);
return getrev(n / 10, initvalue);
}
Below is the answer in swift. It reads number from left and right side and compare them if they are same. Doing this way we will never face a problem of integer overflow (which can occure on reversing number method) as we are not creating another number.
Steps:
- Get length of number
- Loop from length + 1(first) --> 0
- Get ith digit & get last digit
- if both digits are not equal return false as number is not palindrome
- i --
- discard last digit from num (num = num / 10)
end of loo return true
func isPalindrom(_ input: Int) -> Bool { if input < 0 { return false } if input < 10 { return true } var num = input let length = Int(log10(Float(input))) + 1 var i = length while i > 0 && num > 0 { let ithDigit = (input / Int(pow(10.0, Double(i) - 1.0)) ) % 10 let r = Int(num % 10) if ithDigit != r { return false } num = num / 10 i -= 1 } return true }
public static boolean isPalindrome(int x) {
int newX = x;
int newNum = 0;
boolean result = false;
if (x >= 0) {
while (newX >= 10) {
newNum = newNum+newX % 10;
newNum = newNum * 10;
newX = newX / 10;
}
newNum += newX;
if(newNum==x) {
result = true;
}
else {
result=false;
}
}
else {
result = false;
}
return result;
}
public boolean isPalindrome(int x) {
if (isNegative(x))
return false;
boolean isPalindrome = reverseNumber(x) == x ? true : false;
return isPalindrome;
}
private boolean isNegative(int x) {
if (x < 0)
return true;
return false;
}
public int reverseNumber(int x) {
int reverseNumber = 0;
while (x > 0) {
int remainder = x % 10;
reverseNumber = reverseNumber * 10 + remainder;
x = x / 10;
}
return reverseNumber;
}
This solution is quite efficient, since I am using StringBuilder which means that the StringBuilder Class is implemented as a mutable sequence of characters. This means that you append new Strings or chars onto a StringBuilder.
public static boolean isPal(String ss){
StringBuilder stringBuilder = new StringBuilder(ss);
stringBuilder.reverse();
return ss.equals(stringBuilder.toString());
}
I think the best solution provided here https://stackoverflow.com/a/199203/5704551
The coding implementation of this solution can be something like:
var palindromCheck(nums) = () => {
let str = x.toString()
// + before str is quick syntax to cast String To Number.
return nums === +str.split("").reverse().join("")
}
Related