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).
This question is related to
algorithm
language-agnostic
To check the given number is Palindrome or not (Java Code)
class CheckPalindrome{
public static void main(String str[]){
int a=242, n=a, b=a, rev=0;
while(n>0){
a=n%10; n=n/10;rev=rev*10+a;
System.out.println(a+" "+n+" "+rev); // to see the logic
}
if(rev==b) System.out.println("Palindrome");
else System.out.println("Not Palindrome");
}
}
it seems like the easest thing would be to find the opposit number and compare the two:
int max =(int)(Math.random()*100001);
int i;
int num = max; //a var used in the tests
int size; //the number of digits in the original number
int opos = 0; // the oposite number
int nsize = 1;
System.out.println(max);
for(i = 1; num>10; i++)
{
num = num/10;
}
System.out.println("this number has "+i+" digits");
size = i; //setting the digit number to a var for later use
num = max;
for(i=1;i<size;i++)
{
nsize *=10;
}
while(num>1)
{
opos += (num%10)*nsize;
num/=10;
nsize/=10;
}
System.out.println("and the number backwards is "+opos);
if (opos == max )
{
System.out.println("palindrome!!");
}
else
{
System.out.println("aint no palindrome!");
}
Dammit, I’m mad!
http://www.palindromelist.net/palindromes-d/
Single steps example: is 332 a palindromic number?
n = 332
q = n / 10 = 33
r = n - 10 * q = 2
r > 0
r != q
n = q = 33
n > r
q = n / 10 = 3
r -= q = 4294967295
r *= 10 = 4294967286
r += n = 23
r != n
r != q
n = q = 3
n > r ? No, so 332 isn't a palindromic number.
Overflow isn't a problem either. Two divisions were necessary, in code (C#) they're done with multiplications. A n-digit number: ~n/2 divisions!
const ulong c0 = 0xcccccccdUL;
static bool isPal(uint n)
{
if (n < 10) return true;
uint q = (uint)(c0 * n >> 35);
uint r = n - 10 * q;
if (r == 0) return false;
if (r == q) return true;
n = q;
while (n > r)
{
q = (uint)(c0 * n >> 35);
r -= q;
r *= 10;
r += n;
if (r == n || r == q) return true;
n = q;
}
return false;
}
There are 142948 palindromic numbers < 2^32, their sum is 137275874705916.
using System;
class Program
{
static void Main() // take a break
{
uint n, c; var sw = System.Diagnostics.Stopwatch.StartNew();
n = ~0u; c = 0; sw.Restart(); while (n > 0) if (isPal0(n--)) c++;
Console.WriteLine(sw.Elapsed + " " + c); // 76 s
n = ~0u; c = 0; sw.Restart(); while (n > 0) if (isPal1(n--)) c++;
Console.WriteLine(sw.Elapsed + " " + c); // 42 s
n = ~0u; c = 0; sw.Restart(); while (n > 0) if (isPal2(n--)) c++;
Console.WriteLine(sw.Elapsed + " " + c); // 31 s
Console.Read();
}
static bool isPal0(uint u)
{
uint n = u, rev = 0;
while (n > 0) { uint dig = n % 10; rev = rev * 10 + dig; n /= 10; }
return u == rev;
}
static bool isPal1(uint u)
{
uint n = u, r = 0;
while (n >= 10) r = n + (r - (n /= 10)) * 10;
return u == 10 * r + n;
}
static bool isPal2(uint n)
{
if (n < 10) return true;
uint q = n / 10, r = n - 10 * q;
if (r == 0 || r == q) return r > 0;
while ((n = q) > r)
{
q /= 10; r -= q; r *= 10; r += n;
if (r == n || r == q) return true;
}
return false;
}
}
This one seems to be faster.
using System;
class Program
{
static void Main()
{
uint n, c; var sw = System.Diagnostics.Stopwatch.StartNew();
n = ~0u; c = 0; sw.Restart(); while (n > 0) if (isPal(n--)) c++;
Console.WriteLine(sw.Elapsed + " " + c); // 21 s
Console.Read();
}
static bool isPal(uint n)
{
return n < 100 ? n < 10 || n % 11 == 0 :
n < 1000 ? /* */ n / 100 == n % 10 :
n < 10000 ? n % 11 == 0 && n / 1000 == n % 10 && isP(n) :
n < 100000 ? /* */ n / 10000 == n % 10 && isP(n) :
n < 1000000 ? n % 11 == 0 && n / 100000 == n % 10 && isP(n) :
n < 10000000 ? /* */ n / 1000000 == n % 10 && isP(n) :
n < 100000000 ? n % 11 == 0 && n / 10000000 == n % 10 && isP(n) :
n < 1000000000 ? /* */ n / 100000000 == n % 10 && isP(n) :
n % 11 == 0 && n / 1000000000 == n % 10 && isP(n);
}
static bool isP(uint n)
{
uint q = n / 10, r = n - 10 * q;
do { n = q; q /= 10; r -= q; r *= 10; r += n; } while (r < q);
return r == q || r == n;
}
}
With an almost balanced binary search spaghetti tree.
using System;
class Program
{
static void Main()
{
uint n, c; var sw = System.Diagnostics.Stopwatch.StartNew();
n = c = 0; sw.Restart(); while (n < ~0u) if (isPal(n++)) c++;
Console.WriteLine(sw.Elapsed + " " + c); // 17 s
Console.Read();
}
static bool isPal(uint n)
{
return n < 1000000 ? n < 10000 ? n < 1000 ? n < 100 ?
n < 10 || n % 11 == 0 : n / 100 == n % 10 :
n / 1000 == n % 10 && isP(n) : n < 100000 ?
n / 10000 == n % 10 && isP(n) :
n / 100000 == n % 10 && isP(n) :
n < 100000000 ? n < 10000000 ?
n / 1000000 == n % 10 && isP(n) :
n % 11 == 0 && n / 10000000 == n % 10 && isP(n) :
n < 1000000000 ? n / 100000000 == n % 10 && isP(n) :
n % 11 == 0 && n / 1000000000 == n % 10 && isP(n);
}
static bool isP(uint n)
{
uint q = n / 10, r = n - 10 * q;
do { n = q; q /= 10; r -= q; r *= 10; r += n; } while (r < q);
return r == q || r == n;
}
}
Unbalanced upside down.
using System;
class Program
{
static void Main()
{
uint n, c; var sw = System.Diagnostics.Stopwatch.StartNew();
n = c = 0; sw.Restart(); while (n < ~0u) if (isPal(n++)) c++;
Console.WriteLine(sw.Elapsed + " " + c); // 16 s
Console.Read();
}
static bool isPal(uint n)
{
return
n > 999999999 ? n % 11 == 0 && n / 1000000000 == n % 10 && isP(n) :
n > 99999999 ? n / 100000000 == n % 10 && isP(n) :
n > 9999999 ? n % 11 == 0 && n / 10000000 == n % 10 && isP(n) :
n > 999999 ? n / 1000000 == n % 10 && isP(n) :
n > 99999 ? n % 11 == 0 && n / 100000 == n % 10 && isP(n) :
n > 9999 ? n / 10000 == n % 10 && isP(n) :
n > 999 ? n % 11 == 0 && n / 1000 == n % 10 && isP(n) :
n > 99 ? n / 100 == n % 10 :
n < 10 || n % 11 == 0;
}
static bool isP(uint n)
{
uint q = n / 10, r = n - 10 * q;
do { n = q; q /= 10; r -= q; r *= 10; r += n; } while (r < q);
return r == q || r == n;
}
}
a method with a little better constant factor than @sminks method:
num=n
lastDigit=0;
rev=0;
while (num>rev) {
lastDigit=num%10;
rev=rev*10+lastDigit;
num /=2;
}
if (num==rev) print PALINDROME; exit(0);
num=num*10+lastDigit; // This line is required as a number with odd number of bits will necessary end up being smaller even if it is a palindrome
if (num==rev) print PALINDROME
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 class Numbers
{
public static void main(int givenNum)
{
int n= givenNum
int rev=0;
while(n>0)
{
//To extract the last digit
int digit=n%10;
//To store it in reverse
rev=(rev*10)+digit;
//To throw the last digit
n=n/10;
}
//To check if a number is palindrome or not
if(rev==givenNum)
{
System.out.println(givenNum+"is a palindrome ");
}
else
{
System.out.pritnln(givenNum+"is not a palindrome");
}
}
}
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);
}
I went with the regular approach by converting number to string and then further converting string to charArray. Traversing through charArray and find if number at positions are equal or not. Note-: Not reversing the string.
public bool IsPalindrome(int num)
{
string st = num.ToString();
char[] arr = st.ToCharArray();
int len = arr.Length;
if (len <= 1)
{
return false;
}
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] == arr[len - 1])
{
if (i >= len)
{
return true;
}
len--;
}
else
{
break;
}
}
return false;
here's a f# version:
let reverseNumber n =
let rec loop acc = function
|0 -> acc
|x -> loop (acc * 10 + x % 10) (x/10)
loop 0 n
let isPalindrome = function
| x when x = reverseNumber x -> true
| _ -> false
let isPalindrome (n:int) =
let l1 = n.ToString() |> List.ofSeq |> List.rev
let rec isPalindromeInt l1 l2 =
match (l1,l2) with
| (h1::rest1,h2::rest2) -> if (h1 = h2) then isPalindromeInt rest1 rest2 else false
| _ -> true
isPalindromeInt l1 (n.ToString() |> List.ofSeq)
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;
}
Here is a solution usings lists as stacks in python :
def isPalindromicNum(n):
"""
is 'n' a palindromic number?
"""
ns = list(str(n))
for n in ns:
if n != ns.pop():
return False
return True
popping the stack only considers the rightmost side of the number for comparison and it fails fast to reduce checks
Simply get the digit count of the number via Math functions and then iterate by using '/' and '%' operations as follows. After x = (x % divider) / 10, we should divide divider by 100 since we made 2 zero operations.
public static boolean isPalindrome(int x) {
if (x < 0) return false;
if (x < 10) return true;
int numDigits = (int)(Math.log10(x)+1);
int divider = (int) (Math.pow(10, numDigits - 1));
for (int i = 0; i < numDigits / 2; i++) {
if (x / divider != x % 10)
return false;
x = (x % divider) / 10;
divider /= 100;
}
return true;
}
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;
}
This code converts int to String and then checks if the string is pallindrome. The advantage is that it is fast, the disadvantage being that it converts int to String thereby compromising with the perfect solution to question.
static int pallindrome=41012;
static String pallindromer=(Integer.toString(pallindrome));
static int length=pallindromer.length();
public static void main(String[] args) {
pallindrome(0);
System.out.println("It's a pallindrome");
}
static void pallindrome(int index){
if(pallindromer.charAt(index)==pallindromer.charAt(length-(index+1))){
if(index<length-1){
pallindrome(++index);
}
}
else{
System.out.println("Not a pallindrome");
System.exit(0);
}
}
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;
Golang version:
package main
import "fmt"
func main() {
n := 123454321
r := reverse(n)
fmt.Println(r == n)
}
func reverse(n int) int {
r := 0
for {
if n > 0 {
r = r*10 + n%10
n = n / 10
} else {
break
}
}
return r
}
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 code converts int to String and then checks if the string is pallindrome. The advantage is that it is fast, the disadvantage being that it converts int to String thereby compromising with the perfect solution to question.
static int pallindrome=41012;
static String pallindromer=(Integer.toString(pallindrome));
static int length=pallindromer.length();
public static void main(String[] args) {
pallindrome(0);
System.out.println("It's a pallindrome");
}
static void pallindrome(int index){
if(pallindromer.charAt(index)==pallindromer.charAt(length-(index+1))){
if(index<length-1){
pallindrome(++index);
}
}
else{
System.out.println("Not a pallindrome");
System.exit(0);
}
}
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;
A number is palindromic if its string representation is palindromic:
def is_palindrome(s):
return all(s[i] == s[-(i + 1)] for i in range(len(s)//2))
def number_palindrome(n):
return is_palindrome(str(n))
Not sure if this is the best answer, and I'm new at programming. (it's in java)
import java.util.*;
public class Palin {
public static void main(String[] args) {
Random randInt = new Random();
Scanner kbd = new Scanner(System.in);
int t = kbd.nextInt(); //# of test cases;
String[] arrPalin = new String[t]; //array of inputs;
String[] nextPalin = new String[t];
for (int i = 0; i < t; i++) {
arrPalin[i] = String.valueOf(randInt.nextInt(2147483646) + 1);
System.out.println(arrPalin[i]);
}
final long startTime = System.nanoTime();
for (int i = 0; i < t; i++) {
nextPalin[i] = (unmatcher(incrementer(switcher(match(arrPalin[i])))));
}
final long duration = System.nanoTime() - startTime;
for (int i = 0; i < t; i++) {
System.out.println(nextPalin[i]);
}
System.out.println(duration);
}
public static String match(String N) {
int length = N.length();
//Initialize a string with length of N
char[] chars = new char[length];
Arrays.fill(chars, '0');
int count = 1;
for (int i = 0; i < length; i++) {
if ((i%2) == 0) { //at i = even.
if (i == 0) {
chars[i] = N.charAt(i);
} else
chars[i] = N.charAt(i/2);
} else //at i = odd
chars[i] = N.charAt(length - count);
count++;
}
return String.valueOf(chars);
}
public static String switcher(String N) {
int length = N.length();
char[] chars = new char[length];
Arrays.fill(chars, '0');
for (int i = 0; i < length; i++) {
if (i != 0) {
if ((i % 2) == 0) {
chars[i] = N.charAt(i);
} else if ((i % 2) != 0) {
chars[i] = N.charAt(i - 1);
}
}
if (i == 0) {
chars[0] = N.charAt(0);
}
}
return String.valueOf(chars);
}
public static String incrementer(String N) {
int length = N.length();
char[] chars = new char[length];
Arrays.fill(chars, '0');
char[] newN = N.toCharArray();
String returnVal;
int numOne, numTwo;
if ((length % 2) == 0) {
numOne = N.charAt(length-1);
numTwo = N.charAt(length-2);
newN[length-1] = (char)(numOne+1);
newN[length-2] = (char)(numTwo+1);
returnVal = String.valueOf(newN);
} else {
numOne = N.charAt(length-1);
newN[length-1] = (char)(numOne+1);
returnVal = String.valueOf(newN);
}
return returnVal;
}
public static String unmatcher(String N) {
int length = N.length();
char[] chars = new char[length];
Arrays.fill(chars, '0');
char[] newN = N.toCharArray();
for (int i = 0; i < length; i++) {
if (((i % 2) == 0) && (i != 0)) { // for i > 0, even
newN[i / 2] = N.charAt(i);
} else if ((i % 2) == 0 && (i == 0)) { // for i = 0
newN[0] = N.charAt(0);
}
}
for (int i = (length/2); i < length; i++) {
newN[i] = newN[Math.abs(i - (length - 1))];
}
return String.valueOf(newN);
}
}
So for this code, input a number (I did random numbers of how many I want), it will convert, for example the input is 172345 to 157423. Then it will change it to 117722, then if even make it 117733, if odd do the same for the only the last digit. Then make it 173371. It's not specifically finding a palindrome, but it's finding the next highest palindrome number.
Here is one more solution in c++ using templates . This solution will work for case insensitive palindrome string comparison .
template <typename bidirection_iter>
bool palindrome(bidirection_iter first, bidirection_iter last)
{
while(first != last && first != --last)
{
if(::toupper(*first) != ::toupper(*last))
return false;
else
first++;
}
return true;
}
except making the number a string and then reversing the string.
Why dismiss that solution? It's easy to implement and readable. If you were asked with no computer at hand whether 2**10-23 is a decimal palindrome, you'd surely test it by writing it out in decimal.
In Python at least, the slogan 'string operations are slower than arithmetic' is actually false. I compared Smink's arithmetical algorithm to simple string reversal int(str(i)[::-1]). There was no significant difference in speed - it happened string reversal was marginally faster.
In compiled languages (C/C++) the slogan might hold, but one risks overflow errors with large numbers.
def reverse(n):
rev = 0
while n > 0:
rev = rev * 10 + n % 10
n = n // 10
return rev
upper = 10**6
def strung():
for i in range(upper):
int(str(i)[::-1])
def arithmetic():
for i in range(upper):
reverse(i)
import timeit
print "strung", timeit.timeit("strung()", setup="from __main__ import strung", number=1)
print "arithmetic", timeit.timeit("arithmetic()", setup="from __main__ import arithmetic", number=1)
Results in seconds (lower is better):
strung 1.50960231881 arithmetic 1.69729960569
public static void main(String args[])
{
System.out.print("Enter a number: ");
Scanner input = new Scanner(System.in);
int num = input.nextInt();
int number = num;
int reversenum = 0;
while (num != 0)
{
reversenum = reversenum * 10;
reversenum = reversenum + num % 10;
num = num / 10;
}
if (number == reversenum)
System.out.println("The reverse number is " + reversenum + "\nThen the number is palindrome.");
else
System.out.println("The reverse number is " + reversenum + "\nThen the number is not palindrome.");
}
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.
a method with a little better constant factor than @sminks method:
num=n
lastDigit=0;
rev=0;
while (num>rev) {
lastDigit=num%10;
rev=rev*10+lastDigit;
num /=2;
}
if (num==rev) print PALINDROME; exit(0);
num=num*10+lastDigit; // This line is required as a number with odd number of bits will necessary end up being smaller even if it is a palindrome
if (num==rev) print PALINDROME
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;
}
public class PalindromePrime {
private static int g ,n =0,i,m ;
private javax.swing.JTextField jTextField;
static String b ="";
private static Scanner scanner = new Scanner( System.in );
public static void main(String [] args) throws IOException {
System.out.print(" Please Inter Data : ");
g = scanner.nextInt();
System.out.print(" Please Inter Data 2 : ");
m = scanner.nextInt();
count(g,m);
}
public static int count(int L, int R) {
int resultNum = 0;
for( i= L ; i<= R ;i++){
int count= 0 ;
for( n = i ; n >=1 ;n -- ){
if(i%n==0){
count = count + 1 ;
// System.out.println(" Data : \n " +count );
}
}
if(count == 2)
{
//b = b +i + "" ;
String ss= String .valueOf(i);
// System.out.print("\n" +i );
if(isPalindrome(i))
{
//0 System.out.println("Number : " + i + " is a palindrome");
//number2[b] = Integer.parseInt(number_ayy[b]);
//String s = String .valueOf(i);
//System.out.printf("123456", s);
resultNum++;
}
else{
//*System.out.println("Number : " + i + " is Not a palindrome");
}
//System.out.println(" Data : \n " +ss.length() );
}
// palindrome(i);
}
// System.out.print(" Data : ");
// System.out.println(" Data : \n " +b );
return resultNum;
}
@SuppressWarnings("unused")
public static boolean isPalindrome(int number ) {
int p = number; // ?????? p ???? int ?????????? number ??? ?????? ????? method
int r = 0; //?????? r ???? int ??????????????????????????? 0
int w = 0 ;
while (p != 0) { // ???????? While ??? p ?????????? 0 ???? 2!= 0 ???? ????
w = p % 10; // ????????? ??? W ??? ?????????? p ???????? parramiter ??? & mod ??? 10 ??? ???? 2 % 10 = 2 ; w= 2 ; 3% 10 ; w =3
r = r * 10 + w; // (??? R ???????? ????????????????? ???? * 10) + w ?????????? w = p % 10; ??? mod ??? ???? 0*10 + 2 = 2
p = p / 10; //??????? p ???????????? paramiter ????????? 10 ????????????? ?????????????????????????? || ???????????????? 0 ?????????????????????
}
// 1 ???????????? (p != 0) ??????? ??? p ????? p = number ????????
// 2 r = (r * 10) + (p%10) ;
//3 p = p /10 ; ????????? ????????????? 0 ????????? Loop
if (number == r) {
// for(int count = 0 ; count <i ;count ++){
String s1 = String.valueOf(i);
//countLines(s1);
System.out.println("Number : " + "'"+s1 +"'"+" is a palindrome");
return true; //????? return ??
}
return false;
}
public static int countLines(String str)
{
if (str == null || str.length() == 0)
return 0;
int lines = 1;
int len = str.length();
for( int pos = 0; pos < len; pos++) {
char c = str.charAt(pos);
if( c == '\r' ) {
System.out.println("Line 0 : " + "'"+str );
lines++;
if ( pos+1 < len && str.charAt(pos+1) == '\n' )
System.out.println("Line : " + "'"+str );
pos++;
} else if( c == '\n' ) {
lines++;
System.out.println("Line 2 : " + "'"+str );
}
}
return lines;
}
public static int countLines1(String sd) throws IOException {
LineNumberReader lineNumberReader = new LineNumberReader(new StringReader(sd));
int count = 0 ;
System.out.printf("Line : " , count = count + 1 );
lineNumberReader.skip(Long.MAX_VALUE);
return lineNumberReader.getLineNumber();
}
}
Push each individual digit onto a stack, then pop them off. If it's the same forwards and back, it's a palindrome.
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());
}
Not sure if this is the best answer, and I'm new at programming. (it's in java)
import java.util.*;
public class Palin {
public static void main(String[] args) {
Random randInt = new Random();
Scanner kbd = new Scanner(System.in);
int t = kbd.nextInt(); //# of test cases;
String[] arrPalin = new String[t]; //array of inputs;
String[] nextPalin = new String[t];
for (int i = 0; i < t; i++) {
arrPalin[i] = String.valueOf(randInt.nextInt(2147483646) + 1);
System.out.println(arrPalin[i]);
}
final long startTime = System.nanoTime();
for (int i = 0; i < t; i++) {
nextPalin[i] = (unmatcher(incrementer(switcher(match(arrPalin[i])))));
}
final long duration = System.nanoTime() - startTime;
for (int i = 0; i < t; i++) {
System.out.println(nextPalin[i]);
}
System.out.println(duration);
}
public static String match(String N) {
int length = N.length();
//Initialize a string with length of N
char[] chars = new char[length];
Arrays.fill(chars, '0');
int count = 1;
for (int i = 0; i < length; i++) {
if ((i%2) == 0) { //at i = even.
if (i == 0) {
chars[i] = N.charAt(i);
} else
chars[i] = N.charAt(i/2);
} else //at i = odd
chars[i] = N.charAt(length - count);
count++;
}
return String.valueOf(chars);
}
public static String switcher(String N) {
int length = N.length();
char[] chars = new char[length];
Arrays.fill(chars, '0');
for (int i = 0; i < length; i++) {
if (i != 0) {
if ((i % 2) == 0) {
chars[i] = N.charAt(i);
} else if ((i % 2) != 0) {
chars[i] = N.charAt(i - 1);
}
}
if (i == 0) {
chars[0] = N.charAt(0);
}
}
return String.valueOf(chars);
}
public static String incrementer(String N) {
int length = N.length();
char[] chars = new char[length];
Arrays.fill(chars, '0');
char[] newN = N.toCharArray();
String returnVal;
int numOne, numTwo;
if ((length % 2) == 0) {
numOne = N.charAt(length-1);
numTwo = N.charAt(length-2);
newN[length-1] = (char)(numOne+1);
newN[length-2] = (char)(numTwo+1);
returnVal = String.valueOf(newN);
} else {
numOne = N.charAt(length-1);
newN[length-1] = (char)(numOne+1);
returnVal = String.valueOf(newN);
}
return returnVal;
}
public static String unmatcher(String N) {
int length = N.length();
char[] chars = new char[length];
Arrays.fill(chars, '0');
char[] newN = N.toCharArray();
for (int i = 0; i < length; i++) {
if (((i % 2) == 0) && (i != 0)) { // for i > 0, even
newN[i / 2] = N.charAt(i);
} else if ((i % 2) == 0 && (i == 0)) { // for i = 0
newN[0] = N.charAt(0);
}
}
for (int i = (length/2); i < length; i++) {
newN[i] = newN[Math.abs(i - (length - 1))];
}
return String.valueOf(newN);
}
}
So for this code, input a number (I did random numbers of how many I want), it will convert, for example the input is 172345 to 157423. Then it will change it to 117722, then if even make it 117733, if odd do the same for the only the last digit. Then make it 173371. It's not specifically finding a palindrome, but it's finding the next highest palindrome number.
Fastest way I know:
bool is_pal(int n) {
if (n % 10 == 0) return 0;
int r = 0;
while (r < n) {
r = 10 * r + n % 10;
n /= 10;
}
return n == r || n == r / 10;
}
I always use this python solution due to its compactness.
def isPalindrome(number):
return int(str(number)[::-1])==number
checkPalindrome(int number)
{
int lsd, msd,len;
len = log10(number);
while(number)
{
msd = (number/pow(10,len)); // "most significant digit"
lsd = number%10; // "least significant digit"
if(lsd==msd)
{
number/=10; // change of LSD
number-=msd*pow(10,--len); // change of MSD, due to change of MSD
len-=1; // due to change in LSD
} else {return 1;}
}
return 0;
}
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.
Dammit, I’m mad!
http://www.palindromelist.net/palindromes-d/
Single steps example: is 332 a palindromic number?
n = 332
q = n / 10 = 33
r = n - 10 * q = 2
r > 0
r != q
n = q = 33
n > r
q = n / 10 = 3
r -= q = 4294967295
r *= 10 = 4294967286
r += n = 23
r != n
r != q
n = q = 3
n > r ? No, so 332 isn't a palindromic number.
Overflow isn't a problem either. Two divisions were necessary, in code (C#) they're done with multiplications. A n-digit number: ~n/2 divisions!
const ulong c0 = 0xcccccccdUL;
static bool isPal(uint n)
{
if (n < 10) return true;
uint q = (uint)(c0 * n >> 35);
uint r = n - 10 * q;
if (r == 0) return false;
if (r == q) return true;
n = q;
while (n > r)
{
q = (uint)(c0 * n >> 35);
r -= q;
r *= 10;
r += n;
if (r == n || r == q) return true;
n = q;
}
return false;
}
There are 142948 palindromic numbers < 2^32, their sum is 137275874705916.
using System;
class Program
{
static void Main() // take a break
{
uint n, c; var sw = System.Diagnostics.Stopwatch.StartNew();
n = ~0u; c = 0; sw.Restart(); while (n > 0) if (isPal0(n--)) c++;
Console.WriteLine(sw.Elapsed + " " + c); // 76 s
n = ~0u; c = 0; sw.Restart(); while (n > 0) if (isPal1(n--)) c++;
Console.WriteLine(sw.Elapsed + " " + c); // 42 s
n = ~0u; c = 0; sw.Restart(); while (n > 0) if (isPal2(n--)) c++;
Console.WriteLine(sw.Elapsed + " " + c); // 31 s
Console.Read();
}
static bool isPal0(uint u)
{
uint n = u, rev = 0;
while (n > 0) { uint dig = n % 10; rev = rev * 10 + dig; n /= 10; }
return u == rev;
}
static bool isPal1(uint u)
{
uint n = u, r = 0;
while (n >= 10) r = n + (r - (n /= 10)) * 10;
return u == 10 * r + n;
}
static bool isPal2(uint n)
{
if (n < 10) return true;
uint q = n / 10, r = n - 10 * q;
if (r == 0 || r == q) return r > 0;
while ((n = q) > r)
{
q /= 10; r -= q; r *= 10; r += n;
if (r == n || r == q) return true;
}
return false;
}
}
This one seems to be faster.
using System;
class Program
{
static void Main()
{
uint n, c; var sw = System.Diagnostics.Stopwatch.StartNew();
n = ~0u; c = 0; sw.Restart(); while (n > 0) if (isPal(n--)) c++;
Console.WriteLine(sw.Elapsed + " " + c); // 21 s
Console.Read();
}
static bool isPal(uint n)
{
return n < 100 ? n < 10 || n % 11 == 0 :
n < 1000 ? /* */ n / 100 == n % 10 :
n < 10000 ? n % 11 == 0 && n / 1000 == n % 10 && isP(n) :
n < 100000 ? /* */ n / 10000 == n % 10 && isP(n) :
n < 1000000 ? n % 11 == 0 && n / 100000 == n % 10 && isP(n) :
n < 10000000 ? /* */ n / 1000000 == n % 10 && isP(n) :
n < 100000000 ? n % 11 == 0 && n / 10000000 == n % 10 && isP(n) :
n < 1000000000 ? /* */ n / 100000000 == n % 10 && isP(n) :
n % 11 == 0 && n / 1000000000 == n % 10 && isP(n);
}
static bool isP(uint n)
{
uint q = n / 10, r = n - 10 * q;
do { n = q; q /= 10; r -= q; r *= 10; r += n; } while (r < q);
return r == q || r == n;
}
}
With an almost balanced binary search spaghetti tree.
using System;
class Program
{
static void Main()
{
uint n, c; var sw = System.Diagnostics.Stopwatch.StartNew();
n = c = 0; sw.Restart(); while (n < ~0u) if (isPal(n++)) c++;
Console.WriteLine(sw.Elapsed + " " + c); // 17 s
Console.Read();
}
static bool isPal(uint n)
{
return n < 1000000 ? n < 10000 ? n < 1000 ? n < 100 ?
n < 10 || n % 11 == 0 : n / 100 == n % 10 :
n / 1000 == n % 10 && isP(n) : n < 100000 ?
n / 10000 == n % 10 && isP(n) :
n / 100000 == n % 10 && isP(n) :
n < 100000000 ? n < 10000000 ?
n / 1000000 == n % 10 && isP(n) :
n % 11 == 0 && n / 10000000 == n % 10 && isP(n) :
n < 1000000000 ? n / 100000000 == n % 10 && isP(n) :
n % 11 == 0 && n / 1000000000 == n % 10 && isP(n);
}
static bool isP(uint n)
{
uint q = n / 10, r = n - 10 * q;
do { n = q; q /= 10; r -= q; r *= 10; r += n; } while (r < q);
return r == q || r == n;
}
}
Unbalanced upside down.
using System;
class Program
{
static void Main()
{
uint n, c; var sw = System.Diagnostics.Stopwatch.StartNew();
n = c = 0; sw.Restart(); while (n < ~0u) if (isPal(n++)) c++;
Console.WriteLine(sw.Elapsed + " " + c); // 16 s
Console.Read();
}
static bool isPal(uint n)
{
return
n > 999999999 ? n % 11 == 0 && n / 1000000000 == n % 10 && isP(n) :
n > 99999999 ? n / 100000000 == n % 10 && isP(n) :
n > 9999999 ? n % 11 == 0 && n / 10000000 == n % 10 && isP(n) :
n > 999999 ? n / 1000000 == n % 10 && isP(n) :
n > 99999 ? n % 11 == 0 && n / 100000 == n % 10 && isP(n) :
n > 9999 ? n / 10000 == n % 10 && isP(n) :
n > 999 ? n % 11 == 0 && n / 1000 == n % 10 && isP(n) :
n > 99 ? n / 100 == n % 10 :
n < 10 || n % 11 == 0;
}
static bool isP(uint n)
{
uint q = n / 10, r = n - 10 * q;
do { n = q; q /= 10; r -= q; r *= 10; r += n; } while (r < q);
return r == q || r == n;
}
}
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.
Push each individual digit onto a stack, then pop them off. If it's the same forwards and back, it's a palindrome.
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.
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.
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.
Golang version:
package main
import "fmt"
func main() {
n := 123454321
r := reverse(n)
fmt.Println(r == n)
}
func reverse(n int) int {
r := 0
for {
if n > 0 {
r = r*10 + n%10
n = n / 10
} else {
break
}
}
return r
}
Personally I do it this way, and there's no overlap; the code stops checking for matching characters in the correct spot whether the string has an even or odd length. Some of the other methods posted above will attempt to match one extra time when it doesn't need to.
If we use length/2, it will still work but it will do one additional check that it doesn't need to do. For instance, "pop" is 3 in length. 3/2 = 1.5, so it will stop checking when i = 2(since 1<1.5 it will check when i = 1 as well) but we need it to stop at 0, not one. The first "p" is in position 0, and it will check itself against length-1-0(current position) which is the last "p" in position 2, and then we are left with the center letter that needs no checking. When we do length/2 we stop at 1, so what happens is an extra check is performed with i being on the 1 position(the "o") and compares it to itself (length-1-i).
// Checks if our string is palindromic.
var ourString = "A Man, /.,.()^&*A Plan, A Canal__-Panama!";
isPalin(ourString);
function isPalin(string) {
// Make all lower case for case insensitivity and replace all spaces, underscores and non-words.
string = string.toLowerCase().replace(/\s+/g, "").replace(/\W/g,"").replace(/_/g,"");
for(i=0; i<=Math.floor(string.length/2-1); i++) {
if(string[i] !== string[string.length-1-i]) {
console.log("Your string is not palindromic!");
break;
} else if(i === Math.floor(string.length/2-1)) {
console.log("Your string is palindromic!");
}
}
}
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;
}
Push each individual digit onto a stack, then pop them off. If it's the same forwards and back, it's a palindrome.
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;
}
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)
Here is a solution usings lists as stacks in python :
def isPalindromicNum(n):
"""
is 'n' a palindromic number?
"""
ns = list(str(n))
for n in ns:
if n != ns.pop():
return False
return True
popping the stack only considers the rightmost side of the number for comparison and it fails fast to reduce checks
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)
Above most of the answers having a trivial problem is that the int variable possibly might overflow.
Refer to http://articles.leetcode.com/palindrome-number/
boolean isPalindrome(int x) {
if (x < 0)
return false;
int div = 1;
while (x / div >= 10) {
div *= 10;
}
while (x != 0) {
int l = x / div;
int r = x % 10;
if (l != r)
return false;
x = (x % div) / 10;
div /= 100;
}
return true;
}
A lot of the solutions posted here reverses the integer and stores it in a variable which uses extra space which is O(n), but here is a solution with O(1) space.
def isPalindrome(num):
if num < 0:
return False
if num == 0:
return True
from math import log10
length = int(log10(num))
while length > 0:
right = num % 10
left = num / 10**length
if right != left:
return False
num %= 10**length
num /= 10
length -= 2
return True
Personally I do it this way, and there's no overlap; the code stops checking for matching characters in the correct spot whether the string has an even or odd length. Some of the other methods posted above will attempt to match one extra time when it doesn't need to.
If we use length/2, it will still work but it will do one additional check that it doesn't need to do. For instance, "pop" is 3 in length. 3/2 = 1.5, so it will stop checking when i = 2(since 1<1.5 it will check when i = 1 as well) but we need it to stop at 0, not one. The first "p" is in position 0, and it will check itself against length-1-0(current position) which is the last "p" in position 2, and then we are left with the center letter that needs no checking. When we do length/2 we stop at 1, so what happens is an extra check is performed with i being on the 1 position(the "o") and compares it to itself (length-1-i).
// Checks if our string is palindromic.
var ourString = "A Man, /.,.()^&*A Plan, A Canal__-Panama!";
isPalin(ourString);
function isPalin(string) {
// Make all lower case for case insensitivity and replace all spaces, underscores and non-words.
string = string.toLowerCase().replace(/\s+/g, "").replace(/\W/g,"").replace(/_/g,"");
for(i=0; i<=Math.floor(string.length/2-1); i++) {
if(string[i] !== string[string.length-1-i]) {
console.log("Your string is not palindromic!");
break;
} else if(i === Math.floor(string.length/2-1)) {
console.log("Your string is palindromic!");
}
}
}
Try this:
print('!* To Find Palindrome Number')
def Palindrome_Number():
n = input('Enter Number to check for palindromee')
m=n
a = 0
while(m!=0):
a = m % 10 + a * 10
m = m / 10
if( n == a):
print('%d is a palindrome number' %n)
else:
print('%d is not a palindrome number' %n)
just call back the functions
One line python code :
def isPalindrome(number):
return True if str(number) == ''.join(reversed(str(number))) else False
Here is a way.
class Palindrome_Number{
void display(int a){
int count=0;
int n=a;
int n1=a;
while(a>0){
count++;
a=a/10;
}
double b=0.0d;
while(n>0){
b+=(n%10)*(Math.pow(10,count-1));
count--;
n=n/10;
}
if(b==(double)n1){
System.out.println("Palindrome number");
}
else{
System.out.println("Not a palindrome number");
}
}
}
def palindrome(n):
d = []
while (n > 0):
d.append(n % 10)
n //= 10
for i in range(len(d)/2):
if (d[i] != d[-(i+1)]):
return "Fail."
return "Pass."
A lot of the solutions posted here reverses the integer and stores it in a variable which uses extra space which is O(n), but here is a solution with O(1) space.
def isPalindrome(num):
if num < 0:
return False
if num == 0:
return True
from math import log10
length = int(log10(num))
while length > 0:
right = num % 10
left = num / 10**length
if right != left:
return False
num %= 10**length
num /= 10
length -= 2
return True
I didn't notice any answers that solved this problem using no extra space, i.e., all solutions I saw either used a string, or another integer to reverse the number, or some other data structures.
Although languages like Java wrap around on integer overflow, this behavior is undefined in languages like C. (Try reversing 2147483647 (Integer.MAX_VALUE) in Java)
Workaround could to be to use a long or something but, stylistically, I don't quite like that approach.
Now, the concept of a palindromic number is that the number should read the same forwards and backwards. Great. Using this information, we can compare the first digit and the last digit. Trick is, for the first digit, we need the order of the number. Say, 12321. Dividing this by 10000 would get us the leading 1. The trailing 1 can be retrieved by taking the mod with 10. Now, to reduce this to 232. (12321 % 10000)/10 = (2321)/10 = 232. And now, the 10000 would need to be reduced by a factor of 2. So, now on to the Java code...
private static boolean isPalindrome(int n) {
if (n < 0)
return false;
int div = 1;
// find the divisor
while (n / div >= 10)
div *= 10;
// any number less than 10 is a palindrome
while (n != 0) {
int leading = n / div;
int trailing = n % 10;
if (leading != trailing)
return false;
// % with div gets rid of leading digit
// dividing result by 10 gets rid of trailing digit
n = (n % div) / 10;
// got rid of 2 numbers, update div accordingly
div /= 100;
}
return true;
}
Edited as per Hardik's suggestion to cover the cases where there are zeroes in the number.
num = int(raw_input())
list_num = list(str(num))
if list_num[::-1] == list_num:
print "Its a palindrome"
else:
print "Its not a palindrom"
int reverse(int num)
{
assert(num >= 0); // for non-negative integers only.
int rev = 0;
while (num != 0)
{
rev = rev * 10 + num % 10;
num /= 10;
}
return rev;
}
This seemed to work too, but did you consider the possibility that the reversed number might overflow? If it overflows, the behavior is language specific (For Java the number wraps around on overflow, but in C/C++ its behavior is undefined). Yuck.
It turns out that comparing from the two ends is easier. First, compare the first and last digit. If they are not the same, it must not be a palindrome. If they are the same, chop off one digit from both ends and continue until you have no digits left, which you conclude that it must be a palindrome.
Now, getting and chopping the last digit is easy. However, getting and chopping the first digit in a generic way requires some thought. The solution below takes care of it.
int isIntPalindrome(int x)
{
if (x < 0)
return 0;
int div = 1;
while (x / div >= 10)
{
div *= 10;
}
while (x != 0)
{
int l = x / div;
int r = x % 10;
if (l != r)
return 0;
x = (x % div) / 10;
div /= 100;
}
return 1;
}
Try this:
print('!* To Find Palindrome Number')
def Palindrome_Number():
n = input('Enter Number to check for palindromee')
m=n
a = 0
while(m!=0):
a = m % 10 + a * 10
m = m / 10
if( n == a):
print('%d is a palindrome number' %n)
else:
print('%d is not a palindrome number' %n)
just call back the functions
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;
}
Above most of the answers having a trivial problem is that the int variable possibly might overflow.
Refer to http://articles.leetcode.com/palindrome-number/
boolean isPalindrome(int x) {
if (x < 0)
return false;
int div = 1;
while (x / div >= 10) {
div *= 10;
}
while (x != 0) {
int l = x / div;
int r = x % 10;
if (l != r)
return false;
x = (x % div) / 10;
div /= 100;
}
return true;
}
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)))))))
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;
}
This is my Java code. Basically comparing the the first and last value of the string and next inner value pair and so forth.
/*Palindrome number*/
String sNumber = "12321";
int l = sNumber.length(); // getting the length of sNumber. In this case its 5
boolean flag = true;
for (int i = 0; i <= l; ++i) {
if (sNumber.charAt(i) != sNumber.charAt((l--) -1)) { //comparing the first and the last values of the string
System.out.println(sNumber +" is not a palindrome number");
flag = false;
break;
}
//l--; // to reducing the length value by 1
}
if (flag) {
System.out.println(sNumber +" is a palindrome number");
}
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());
}
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:
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
}
num = int(raw_input())
list_num = list(str(num))
if list_num[::-1] == list_num:
print "Its a palindrome"
else:
print "Its not a palindrom"
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.
Try this:
reverse = 0;
remainder = 0;
count = 0;
while (number > reverse)
{
remainder = number % 10;
reverse = reverse * 10 + remainder;
number = number / 10;
count++;
}
Console.WriteLine(count);
if (reverse == number)
{
Console.WriteLine("Your number is a palindrome");
}
else
{
number = number * 10 + remainder;
if (reverse == number)
Console.WriteLine("your number is a palindrome");
else
Console.WriteLine("your number is not a palindrome");
}
Console.ReadLine();
}
}
def palindrome(n):
d = []
while (n > 0):
d.append(n % 10)
n //= 10
for i in range(len(d)/2):
if (d[i] != d[-(i+1)]):
return "Fail."
return "Pass."
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);
}
Recursive solution in ruby, without converting the number to string.
def palindrome?(x, a=x, b=0)
return x==b if a<1
palindrome?(x, a/10, b*10 + a%10)
end
palindrome?(55655)
public class PalindromePrime {
private static int g ,n =0,i,m ;
private javax.swing.JTextField jTextField;
static String b ="";
private static Scanner scanner = new Scanner( System.in );
public static void main(String [] args) throws IOException {
System.out.print(" Please Inter Data : ");
g = scanner.nextInt();
System.out.print(" Please Inter Data 2 : ");
m = scanner.nextInt();
count(g,m);
}
public static int count(int L, int R) {
int resultNum = 0;
for( i= L ; i<= R ;i++){
int count= 0 ;
for( n = i ; n >=1 ;n -- ){
if(i%n==0){
count = count + 1 ;
// System.out.println(" Data : \n " +count );
}
}
if(count == 2)
{
//b = b +i + "" ;
String ss= String .valueOf(i);
// System.out.print("\n" +i );
if(isPalindrome(i))
{
//0 System.out.println("Number : " + i + " is a palindrome");
//number2[b] = Integer.parseInt(number_ayy[b]);
//String s = String .valueOf(i);
//System.out.printf("123456", s);
resultNum++;
}
else{
//*System.out.println("Number : " + i + " is Not a palindrome");
}
//System.out.println(" Data : \n " +ss.length() );
}
// palindrome(i);
}
// System.out.print(" Data : ");
// System.out.println(" Data : \n " +b );
return resultNum;
}
@SuppressWarnings("unused")
public static boolean isPalindrome(int number ) {
int p = number; // ?????? p ???? int ?????????? number ??? ?????? ????? method
int r = 0; //?????? r ???? int ??????????????????????????? 0
int w = 0 ;
while (p != 0) { // ???????? While ??? p ?????????? 0 ???? 2!= 0 ???? ????
w = p % 10; // ????????? ??? W ??? ?????????? p ???????? parramiter ??? & mod ??? 10 ??? ???? 2 % 10 = 2 ; w= 2 ; 3% 10 ; w =3
r = r * 10 + w; // (??? R ???????? ????????????????? ???? * 10) + w ?????????? w = p % 10; ??? mod ??? ???? 0*10 + 2 = 2
p = p / 10; //??????? p ???????????? paramiter ????????? 10 ????????????? ?????????????????????????? || ???????????????? 0 ?????????????????????
}
// 1 ???????????? (p != 0) ??????? ??? p ????? p = number ????????
// 2 r = (r * 10) + (p%10) ;
//3 p = p /10 ; ????????? ????????????? 0 ????????? Loop
if (number == r) {
// for(int count = 0 ; count <i ;count ++){
String s1 = String.valueOf(i);
//countLines(s1);
System.out.println("Number : " + "'"+s1 +"'"+" is a palindrome");
return true; //????? return ??
}
return false;
}
public static int countLines(String str)
{
if (str == null || str.length() == 0)
return 0;
int lines = 1;
int len = str.length();
for( int pos = 0; pos < len; pos++) {
char c = str.charAt(pos);
if( c == '\r' ) {
System.out.println("Line 0 : " + "'"+str );
lines++;
if ( pos+1 < len && str.charAt(pos+1) == '\n' )
System.out.println("Line : " + "'"+str );
pos++;
} else if( c == '\n' ) {
lines++;
System.out.println("Line 2 : " + "'"+str );
}
}
return lines;
}
public static int countLines1(String sd) throws IOException {
LineNumberReader lineNumberReader = new LineNumberReader(new StringReader(sd));
int count = 0 ;
System.out.printf("Line : " , count = count + 1 );
lineNumberReader.skip(Long.MAX_VALUE);
return lineNumberReader.getLineNumber();
}
}
To check the given number is Palindrome or not (Java Code)
class CheckPalindrome{
public static void main(String str[]){
int a=242, n=a, b=a, rev=0;
while(n>0){
a=n%10; n=n/10;rev=rev*10+a;
System.out.println(a+" "+n+" "+rev); // to see the logic
}
if(rev==b) System.out.println("Palindrome");
else System.out.println("Not Palindrome");
}
}
public static void main(String args[])
{
System.out.print("Enter a number: ");
Scanner input = new Scanner(System.in);
int num = input.nextInt();
int number = num;
int reversenum = 0;
while (num != 0)
{
reversenum = reversenum * 10;
reversenum = reversenum + num % 10;
num = num / 10;
}
if (number == reversenum)
System.out.println("The reverse number is " + reversenum + "\nThen the number is palindrome.");
else
System.out.println("The reverse number is " + reversenum + "\nThen the number is not palindrome.");
}
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.
here's a f# version:
let reverseNumber n =
let rec loop acc = function
|0 -> acc
|x -> loop (acc * 10 + x % 10) (x/10)
loop 0 n
let isPalindrome = function
| x when x = reverseNumber x -> true
| _ -> false
except making the number a string and then reversing the string.
Why dismiss that solution? It's easy to implement and readable. If you were asked with no computer at hand whether 2**10-23 is a decimal palindrome, you'd surely test it by writing it out in decimal.
In Python at least, the slogan 'string operations are slower than arithmetic' is actually false. I compared Smink's arithmetical algorithm to simple string reversal int(str(i)[::-1]). There was no significant difference in speed - it happened string reversal was marginally faster.
In compiled languages (C/C++) the slogan might hold, but one risks overflow errors with large numbers.
def reverse(n):
rev = 0
while n > 0:
rev = rev * 10 + n % 10
n = n // 10
return rev
upper = 10**6
def strung():
for i in range(upper):
int(str(i)[::-1])
def arithmetic():
for i in range(upper):
reverse(i)
import timeit
print "strung", timeit.timeit("strung()", setup="from __main__ import strung", number=1)
print "arithmetic", timeit.timeit("arithmetic()", setup="from __main__ import arithmetic", number=1)
Results in seconds (lower is better):
strung 1.50960231881 arithmetic 1.69729960569
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;
A number is palindromic if its string representation is palindromic:
def is_palindrome(s):
return all(s[i] == s[-(i + 1)] for i in range(len(s)//2))
def number_palindrome(n):
return is_palindrome(str(n))
I went with the regular approach by converting number to string and then further converting string to charArray. Traversing through charArray and find if number at positions are equal or not. Note-: Not reversing the string.
public bool IsPalindrome(int num)
{
string st = num.ToString();
char[] arr = st.ToCharArray();
int len = arr.Length;
if (len <= 1)
{
return false;
}
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] == arr[len - 1])
{
if (i >= len)
{
return true;
}
len--;
}
else
{
break;
}
}
return false;
checkPalindrome(int number)
{
int lsd, msd,len;
len = log10(number);
while(number)
{
msd = (number/pow(10,len)); // "most significant digit"
lsd = number%10; // "least significant digit"
if(lsd==msd)
{
number/=10; // change of LSD
number-=msd*pow(10,--len); // change of MSD, due to change of MSD
len-=1; // due to change in LSD
} else {return 1;}
}
return 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.
Here is a way.
class Palindrome_Number{
void display(int a){
int count=0;
int n=a;
int n1=a;
while(a>0){
count++;
a=a/10;
}
double b=0.0d;
while(n>0){
b+=(n%10)*(Math.pow(10,count-1));
count--;
n=n/10;
}
if(b==(double)n1){
System.out.println("Palindrome number");
}
else{
System.out.println("Not a palindrome number");
}
}
}
In Python, there is a fast, iterative way.
def reverse(n):
newnum=0
while n>0:
newnum = newnum*10 + n % 10
n//=10
return newnum
def palindrome(n):
return n == reverse(n)
This also prevents memory issues with recursion (like StackOverflow error in Java)
I always use this python solution due to its compactness.
def isPalindrome(number):
return int(str(number)[::-1])==number
This is my Java code. Basically comparing the the first and last value of the string and next inner value pair and so forth.
/*Palindrome number*/
String sNumber = "12321";
int l = sNumber.length(); // getting the length of sNumber. In this case its 5
boolean flag = true;
for (int i = 0; i <= l; ++i) {
if (sNumber.charAt(i) != sNumber.charAt((l--) -1)) { //comparing the first and the last values of the string
System.out.println(sNumber +" is not a palindrome number");
flag = false;
break;
}
//l--; // to reducing the length value by 1
}
if (flag) {
System.out.println(sNumber +" is a palindrome number");
}
it seems like the easest thing would be to find the opposit number and compare the two:
int max =(int)(Math.random()*100001);
int i;
int num = max; //a var used in the tests
int size; //the number of digits in the original number
int opos = 0; // the oposite number
int nsize = 1;
System.out.println(max);
for(i = 1; num>10; i++)
{
num = num/10;
}
System.out.println("this number has "+i+" digits");
size = i; //setting the digit number to a var for later use
num = max;
for(i=1;i<size;i++)
{
nsize *=10;
}
while(num>1)
{
opos += (num%10)*nsize;
num/=10;
nsize/=10;
}
System.out.println("and the number backwards is "+opos);
if (opos == max )
{
System.out.println("palindrome!!");
}
else
{
System.out.println("aint no palindrome!");
}
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.
Fastest way I know:
bool is_pal(int n) {
if (n % 10 == 0) return 0;
int r = 0;
while (r < n) {
r = 10 * r + n % 10;
n /= 10;
}
return n == r || n == r / 10;
}
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;
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:
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
}
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)))))))
public class Numbers
{
public static void main(int givenNum)
{
int n= givenNum
int rev=0;
while(n>0)
{
//To extract the last digit
int digit=n%10;
//To store it in reverse
rev=(rev*10)+digit;
//To throw the last digit
n=n/10;
}
//To check if a number is palindrome or not
if(rev==givenNum)
{
System.out.println(givenNum+"is a palindrome ");
}
else
{
System.out.pritnln(givenNum+"is not a palindrome");
}
}
}
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.
int reverse(int num)
{
assert(num >= 0); // for non-negative integers only.
int rev = 0;
while (num != 0)
{
rev = rev * 10 + num % 10;
num /= 10;
}
return rev;
}
This seemed to work too, but did you consider the possibility that the reversed number might overflow? If it overflows, the behavior is language specific (For Java the number wraps around on overflow, but in C/C++ its behavior is undefined). Yuck.
It turns out that comparing from the two ends is easier. First, compare the first and last digit. If they are not the same, it must not be a palindrome. If they are the same, chop off one digit from both ends and continue until you have no digits left, which you conclude that it must be a palindrome.
Now, getting and chopping the last digit is easy. However, getting and chopping the first digit in a generic way requires some thought. The solution below takes care of it.
int isIntPalindrome(int x)
{
if (x < 0)
return 0;
int div = 1;
while (x / div >= 10)
{
div *= 10;
}
while (x != 0)
{
int l = x / div;
int r = x % 10;
if (l != r)
return 0;
x = (x % div) / 10;
div /= 100;
}
return 1;
}
In Python, there is a fast, iterative way.
def reverse(n):
newnum=0
while n>0:
newnum = newnum*10 + n % 10
n//=10
return newnum
def palindrome(n):
return n == reverse(n)
This also prevents memory issues with recursion (like StackOverflow error in Java)
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;
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;
}
Try this:
reverse = 0;
remainder = 0;
count = 0;
while (number > reverse)
{
remainder = number % 10;
reverse = reverse * 10 + remainder;
number = number / 10;
count++;
}
Console.WriteLine(count);
if (reverse == number)
{
Console.WriteLine("Your number is a palindrome");
}
else
{
number = number * 10 + remainder;
if (reverse == number)
Console.WriteLine("your number is a palindrome");
else
Console.WriteLine("your number is not a palindrome");
}
Console.ReadLine();
}
}
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;
One line python code :
def isPalindrome(number):
return True if str(number) == ''.join(reversed(str(number))) else False
let isPalindrome (n:int) =
let l1 = n.ToString() |> List.ofSeq |> List.rev
let rec isPalindromeInt l1 l2 =
match (l1,l2) with
| (h1::rest1,h2::rest2) -> if (h1 = h2) then isPalindromeInt rest1 rest2 else false
| _ -> true
isPalindromeInt l1 (n.ToString() |> List.ofSeq)
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.
Recursive solution in ruby, without converting the number to string.
def palindrome?(x, a=x, b=0)
return x==b if a<1
palindrome?(x, a/10, b*10 + a%10)
end
palindrome?(55655)
Simply get the digit count of the number via Math functions and then iterate by using '/' and '%' operations as follows. After x = (x % divider) / 10, we should divide divider by 100 since we made 2 zero operations.
public static boolean isPalindrome(int x) {
if (x < 0) return false;
if (x < 10) return true;
int numDigits = (int)(Math.log10(x)+1);
int divider = (int) (Math.pow(10, numDigits - 1));
for (int i = 0; i < numDigits / 2; i++) {
if (x / divider != x % 10)
return false;
x = (x % divider) / 10;
divider /= 100;
}
return true;
}
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 one more solution in c++ using templates . This solution will work for case insensitive palindrome string comparison .
template <typename bidirection_iter>
bool palindrome(bidirection_iter first, bidirection_iter last)
{
while(first != last && first != --last)
{
if(::toupper(*first) != ::toupper(*last))
return false;
else
first++;
}
return true;
}
Source: Stackoverflow.com