Check if a number is Palindrome
Given a positive integer, write a function that returns true if the given number is a palindrome, else false. For example, 12321 is a palindrome, but 1451 is not a palindrome.
Method 1:
Let the given number be num. A simple method for this problem is to first reverse digits of num, then compare the reverse of num with num. If both are same, then return true, else false.
Following is an interesting method inspired from method#2 of this post. The idea is to create a copy of num and recursively pass the copy by reference, and pass num by value. In the recursive calls, divide num by 10 while moving down the recursion tree. While moving up the recursion tree, divide the copy by 10. When they meet in a function for which all child calls are over, the last digit of num will be ith digit from the beginning and the last digit of copy will be ith digit from the end.
C++
// A recursive C++ program to check // whether a given number // is palindrome or not #include <iostream> using namespace std; // A function that returns true only // if num contains one // digit int oneDigit( int num) { // Comparison operation is faster // than division // operation. So using following // instead of "return num // / 10 == 0;" return (num >= 0 && num < 10); } // A recursive function to find // out whether num is // palindrome or not. Initially, dupNum // contains address of // a copy of num. bool isPalUtil( int num, int * dupNum) { // Base case (needed for recursion // termination): This // statement mainly compares the // first digit with the // last digit if (oneDigit(num)) return (num == (*dupNum) % 10); // This is the key line in this // method. Note that all // recursive calls have a separate // copy of num, but they // all share same copy of *dupNum. // We divide num while // moving up the recursion tree if (!isPalUtil(num / 10, dupNum)) return false ; // The following statements are // executed when we move up // the recursion call tree *dupNum /= 10; // At this point, if num%10 contains // i'th digit from // beginning, then (*dupNum)%10 // contains i'th digit // from end return (num % 10 == (*dupNum) % 10); } // The main function that uses // recursive function // isPalUtil() to find out whether // num is palindrome or not int isPal( int num) { // Check if num is negative, // make it positive if (num < 0) num = -num; // Create a separate copy of num, // so that modifications // made to address dupNum don't // change the input number. // *dupNum = num int * dupNum = new int (num); return isPalUtil(num, dupNum); } // Driver program to test // above functions int main() { int n = 12321; isPal(n) ? cout << "Yes\n" : cout << "No" << endl; n = 12; isPal(n) ? cout << "Yes\n" : cout << "No" << endl; n = 88; isPal(n) ? cout << "Yes\n" : cout << "No" << endl; n = 8999; isPal(n) ? cout << "Yes\n" : cout << "No" ; return 0; } // this code is contributed by shivanisinghss2110 |
C
#include <stdio.h> #include <stdbool.h> // A function that returns true only // if num contains one digit int oneDigit( int num) { // Comparison operation is faster // than division operation. // So using the following instead of "return num / 10 == 0;" return (num >= 0 && num < 10); } // A recursive function to find out whether // num is palindrome or not. // Initially, dupNum contains the address of a copy of num. bool isPalUtil( int num, int * dupNum) { // Base case (needed for recursion termination): // This statement mainly compares the first digit with the last digit. if (oneDigit(num)) return (num == (*dupNum) % 10); // This is the key line in this method. // Note that all recursive calls have a separate copy of num, // but they all share the same copy of *dupNum. // We divide num while moving up the recursion tree. if (!isPalUtil(num / 10, dupNum)) return false ; // The following statements are executed when we move up the recursion call tree. *dupNum /= 10; // At this point, if num % 10 contains the i'th digit from the beginning, // then (*dupNum) % 10 contains the i'th digit from the end. return (num % 10 == (*dupNum) % 10); } // The main function that uses the recursive function // isPalUtil() to find out whether num is palindrome or not. bool isPal( int num) { // Check if num is negative, make it positive. if (num < 0) num = -num; // Create a separate copy of num, so that modifications // made to the address dupNum don't change the input number. int dupNum = num; return isPalUtil(num, &dupNum); } // Driver program to test above functions int main() { int n = 12321; isPal(n) ? printf ( "Yes\n" ) : printf ( "No\n" ); n = 12; isPal(n) ? printf ( "Yes\n" ) : printf ( "No\n" ); n = 88; isPal(n) ? printf ( "Yes\n" ) : printf ( "No\n" ); n = 8999; isPal(n) ? printf ( "Yes\n" ) : printf ( "No\n" ); return 0; } |
Java
// A recursive Java program to // check whether a given number // is palindrome or not import java.io.*; import java.util.*; public class CheckPalindromeNumberRecursion { // A function that returns true // only if num contains one digit public static int oneDigit( int num) { if ((num >= 0 ) && (num < 10 )) return 1 ; else return 0 ; } public static int isPalUtil ( int num, int dupNum) throws Exception { // base condition to return once we // move past first digit if (num == 0 ) { return dupNum; } else { dupNum = isPalUtil(num / 10 , dupNum); } // Check for equality of first digit of // num and dupNum if (num % 10 == dupNum % 10 ) { // if first digit values of num and // dupNum are equal divide dupNum // value by 10 to keep moving in sync // with num. return dupNum / 10 ; } else { // At position values are not // matching throw exception and exit. // no need to proceed further. throw new Exception(); } } public static int isPal( int num) throws Exception { if (num < 0 ) num = (-num); int dupNum = (num); return isPalUtil(num, dupNum); } public static void main(String args[]) { int n = 12421 ; try { isPal(n); System.out.println( "Yes" ); } catch (Exception e) { System.out.println( "No" ); } n = 1231 ; try { isPal(n); System.out.println( "Yes" ); } catch (Exception e) { System.out.println( "No" ); } n = 12 ; try { isPal(n); System.out.println( "Yes" ); } catch (Exception e) { System.out.println( "No" ); } n = 88 ; try { isPal(n); System.out.println( "Yes" ); } catch (Exception e) { System.out.println( "No" ); } n = 8999 ; try { isPal(n); System.out.println( "Yes" ); } catch (Exception e) { System.out.println( "No" ); } } } // This code is contributed // by Nasir J |
Python3
# A recursive Python3 program to check # whether a given number is palindrome or not # A function that returns true # only if num contains one digit def oneDigit(num): # comparison operation is faster # than division operation. So # using following instead of # "return num / 10 == 0;" return ((num > = 0 ) and (num < 10 )) # A recursive function to find # out whether num is palindrome # or not. Initially, dupNum # contains address of a copy of num. def isPalUtil(num, dupNum): # Base case (needed for recursion # termination): This statement # mainly compares the first digit # with the last digit if oneDigit(num): return (num = = (dupNum[ 0 ]) % 10 ) # This is the key line in this # method. Note that all recursive # calls have a separate copy of # num, but they all share same # copy of *dupNum. We divide num # while moving up the recursion tree if not isPalUtil(num / / 10 , dupNum): return False # The following statements are # executed when we move up the # recursion call tree dupNum[ 0 ] = dupNum[ 0 ] / / 10 # At this point, if num%10 # contains i'th digit from # beginning, then (*dupNum)%10 # contains i'th digit from end return (num % 10 = = (dupNum[ 0 ]) % 10 ) # The main function that uses # recursive function isPalUtil() # to find out whether num is # palindrome or not def isPal(num): # If num is negative, # make it positive if (num < 0 ): num = ( - num) # Create a separate copy of # num, so that modifications # made to address dupNum # don't change the input number. dupNum = [num] # *dupNum = num return isPalUtil(num, dupNum) # Driver Code n = 12321 if isPal(n): print ( "Yes" ) else : print ( "No" ) n = 12 if isPal(n) : print ( "Yes" ) else : print ( "No" ) n = 88 if isPal(n) : print ( "Yes" ) else : print ( "No" ) n = 8999 if isPal(n) : print ( "Yes" ) else : print ( "No" ) # This code is contributed by mits |
C#
// A recursive C# program to // check whether a given number // is palindrome or not using System; class GFG { // A function that returns true // only if num contains one digit public static int oneDigit( int num) { // comparison operation is // faster than division // operation. So using // following instead of // "return num / 10 == 0;" if ((num >= 0) &&(num < 10)) return 1; else return 0; } // A recursive function to // find out whether num is // palindrome or not. // Initially, dupNum contains // address of a copy of num. public static int isPalUtil( int num, int dupNum) { // Base case (needed for recursion // termination): This statement // mainly compares the first digit // with the last digit if (oneDigit(num) == 1) if (num == (dupNum) % 10) return 1; else return 0; // This is the key line in // this method. Note that // all recursive calls have // a separate copy of num, // but they all share same // copy of *dupNum. We divide // num while moving up the // recursion tree if (isPalUtil(( int )(num / 10), dupNum) == 0) return -1; // The following statements // are executed when we move // up the recursion call tree dupNum = ( int )(dupNum / 10); // At this point, if num%10 // contains i'th digit from // beginning, then (*dupNum)%10 // contains i'th digit from end if (num % 10 == (dupNum) % 10) return 1; else return 0; } // The main function that uses // recursive function isPalUtil() // to find out whether num is // palindrome or not public static int isPal( int num) { // If num is negative, // make it positive if (num < 0) num = (-num); // Create a separate copy // of num, so that modifications // made to address dupNum // don't change the input number. int dupNum = (num); // *dupNum = num return isPalUtil(num, dupNum); } // Driver Code public static void Main() { int n = 12321; if (isPal(n) == 0) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); n = 12; if (isPal(n) == 0) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); n = 88; if (isPal(n) == 1) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); n = 8999; if (isPal(n) == 0) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } // This code is contributed by mits |
Javascript
<script> // A recursive javascript program to // check whether a given number // is palindrome or not // A function that returns true // only if num contains one digit function oneDigit(num) { if ((num >= 0) && (num < 10)) return 1; else return 0; } function isPalUtil (num , dupNum) { // base condition to return once we // move past first digit if (num == 0) { return dupNum; } else { dupNum = isPalUtil(parseInt(num / 10), dupNum); } // Check for equality of first digit of // num and dupNum if (num % 10 == dupNum % 10) { // if first digit values of num and // dupNum are equal divide dupNum // value by 10 to keep moving in sync // with num. return parseInt(dupNum / 10); } else { // At position values are not // matching throw exception and exit. // no need to proceed further. throw e; } } function isPal(num) { if (num < 0) num = (-num); var dupNum = (num); return isPalUtil(num, dupNum); } var n = 1242; try { isPal(n); document.write( "<br>Yes" ); } catch (e) { document.write( "<br>No" ); } n = 1231; try { isPal(n); document.write( "<br>Yes" ); } catch (e) { document.write( "<br>No" ); } n = 12; try { isPal(n); document.write( "<br>Yes" ); } catch (e) { document.write( "<br>No" ); } n = 88; try { isPal(n); document.write( "<br>Yes" ); } catch (e) { document.write( "<br>No" ); } n = 8999; try { isPal(n); document.write( "<br>Yes" ); } catch (e) { document.write( "<br>No" ); } // This code is contributed by Amit Katiyar </script> |
PHP
<?php // A recursive PHP program to // check whether a given number // is palindrome or not // A function that returns true // only if num contains one digit function oneDigit( $num ) { // comparison operation is faster // than division operation. So // using following instead of // "return num / 10 == 0;" return (( $num >= 0) && ( $num < 10)); } // A recursive function to find // out whether num is palindrome // or not. Initially, dupNum // contains address of a copy of num. function isPalUtil( $num , $dupNum ) { // Base case (needed for recursion // termination): This statement // mainly compares the first digit // with the last digit if (oneDigit( $num )) return ( $num == ( $dupNum ) % 10); // This is the key line in this // method. Note that all recursive // calls have a separate copy of // num, but they all share same // copy of *dupNum. We divide num // while moving up the recursion tree if (!isPalUtil((int)( $num / 10), $dupNum )) return -1; // The following statements are // executed when we move up the // recursion call tree $dupNum = (int)( $dupNum / 10); // At this point, if num%10 // contains i'th digit from // beginning, then (*dupNum)%10 // contains i'th digit from end return ( $num % 10 == ( $dupNum ) % 10); } // The main function that uses // recursive function isPalUtil() // to find out whether num is // palindrome or not function isPal( $num ) { // If num is negative, // make it positive if ( $num < 0) $num = (- $num ); // Create a separate copy of // num, so that modifications // made to address dupNum // don't change the input number. $dupNum = ( $num ); // *dupNum = num return isPalUtil( $num , $dupNum ); } // Driver Code $n = 12321; if (isPal( $n ) == 0) echo "Yes\n" ; else echo "No\n" ; $n = 12; if (isPal( $n ) == 0) echo "Yes\n" ; else echo "No\n" ; $n = 88; if (isPal( $n ) == 1) echo "Yes\n" ; else echo "No\n" ; $n = 8999; if (isPal( $n ) == 0) echo "Yes\n" ; else echo "No\n" ; // This code is contributed by m_kit ?> |
Yes No Yes No
Time Complexity: O(log n)
Auxiliary Space: O(log n)
To check a number is palindrome or not without using any extra space
Method 2:Using string() method
- When the number of digits of that number exceeds 1018, we can’t take that number as an integer since the range of long long int doesn’t satisfy the given number.
- So take input as a string, Run a loop from starting to length/2 and check the first character(numeric) to the last character of the string and second to second last one, and so on ….If any character mismatches, the string wouldn’t be a palindrome.
Below is the implementation of the above approach
C++14
// C++ implementation of the above approach #include <iostream> using namespace std; // Function to check palindrome int checkPalindrome(string str) { // Calculating string length int len = str.length(); // Traversing through the string // upto half its length for ( int i = 0; i < len / 2; i++) { // Comparing i th character // from starting and len-i // th character from end if (str[i] != str[len - i - 1]) return false ; } // If the above loop doesn't return then it is // palindrome return true ; } // Driver Code int main() { // taking number as string string st = "112233445566778899000000998877665544332211" ; if (checkPalindrome(st) == true ) cout << "Yes" ; else cout << "No" ; return 0; } // this code is written by vikkycirus |
Java
// Java implementation of the above approach import java.io.*; class GFG{ // Function to check palindrome static boolean checkPalindrome(String str) { // Calculating string length int len = str.length(); // Traversing through the string // upto half its length for ( int i = 0 ; i < len / 2 ; i++) { // Comparing i th character // from starting and len-i // th character from end if (str.charAt(i) != str.charAt(len - i - 1 )) return false ; } // If the above loop doesn't return then // it is palindrome return true ; } // Driver Code public static void main(String[] args) { // Taking number as string String st = "112233445566778899000000998877665544332211" ; if (checkPalindrome(st) == true ) System.out.print( "Yes" ); else System.out.print( "No" ); } } // This code is contributed by subhammahato348 |
Python3
# Python3 implementation of the above approach # function to check palindrome def checkPalindrome( str ): # Run loop from 0 to len/2 for i in range ( 0 , len ( str ) / / 2 ): if str [i] ! = str [ len ( str ) - i - 1 ]: return False # If the above loop doesn't #return then it is palindrome return True # Driver code st = "112233445566778899000000998877665544332211" if (checkPalindrome(st) = = True ): print ( "it is a palindrome" ) else : print ( "It is not a palindrome" ) |
C#
// C# implementation of the above approach using System; class GFG{ // Function to check palindrome static bool checkPalindrome( string str) { // Calculating string length int len = str.Length; // Traversing through the string // upto half its length for ( int i = 0; i < len / 2; i++) { // Comparing i th character // from starting and len-i // th character from end if (str[i] != str[len - i - 1]) return false ; } // If the above loop doesn't return then // it is palindrome return true ; } // Driver Code public static void Main() { // Taking number as string string st = "112233445566778899000000998877665544332211" ; if (checkPalindrome(st) == true ) Console.Write( "Yes" ); else Console.Write( "No" ); } } // This code is contributed by subhammahato348 |
Javascript
<script> // Javascript implementation of the above approach // Function to check palindrome function checkPalindrome(str) { // Calculating string length var len = str.length; // Traversing through the string // upto half its length for ( var i = 0; i < len / 2; i++) { // Comparing ith character // from starting and len-ith // character from end if (str[i] != str[len - i - 1]) return false ; } // If the above loop doesn't return then it is // palindrome return true ; } // Driver Code // taking number as string let st = "112233445566778899000000998877665544332211" ; if (checkPalindrome(st) == true ) document.write( "Yes" ); else document.write( "No" ); // This code is contributed by Mayank Tyagi </script> |
Yes
Time Complexity: O(|str|)
Auxiliary Space: O(1)
Method 3:
Here is the simplest approach to check if a number is Palindrome or not . This approach can be used when the number of digits in the given number is less than 10^18 because if the number of digits of that number exceeds 10^18, we can’t take that number as an integer since the range of long long int doesn’t satisfy the given number.
To check whether the given number is palindrome or not we will just reverse the digits of the given number and check if the reverse of that number is equal to the original number or not . If reverse of number is equal to that number than the number will be Palindrome else it will not a Palindrome.
C++
// C++ program to check if a number is Palindrome #include <iostream> using namespace std; // Function to check Palindrome bool checkPalindrome( int n) { int reverse = 0; int temp = n; while (temp != 0) { reverse = (reverse * 10) + (temp % 10); temp = temp / 10; } return (reverse == n); // if it is true then it will return 1; // else if false it will return 0; } int main() { int n = 7007; if (checkPalindrome(n) == 1) { cout << "Yes\n" ; } else { cout << "No\n" ; } return 0; } // This code is contributed by Suruchi Kumari |
Java
/*package whatever //do not write package name here */ import java.io.*; class GFG { // Java program to check if a number is Palindrome // Function to check Palindrome static boolean checkPalindrome( int n) { int reverse = 0 ; int temp = n; while (temp != 0 ) { reverse = (reverse * 10 ) + (temp % 10 ); temp = temp / 10 ; } return (reverse == n); // if it is true then it will return 1; // else if false it will return 0; } // Driver Code public static void main(String args[]) { int n = 7007 ; if (checkPalindrome(n) == true ) { System.out.println( "Yes" ); } else { System.out.println( "No" ); } } } // This code is contributed by shinjanpatra |
Python3
# Python3 program to check if a number is Palindrome # Function to check Palindrome def checkPalindrome(n): reverse = 0 temp = n while (temp ! = 0 ): reverse = (reverse * 10 ) + (temp % 10 ) temp = temp / / 10 return (reverse = = n) # if it is true then it will return 1; # else if false it will return 0; # driver code n = 7007 if (checkPalindrome(n) = = 1 ): print ( "Yes" ) else : print ( "No" ) # This code is contributed by shinjanpatra |
C#
// C# program to check if a number is Palindrome using System; class GFG { // Function to check Palindrome static bool checkPalindrome( int n) { int reverse = 0; int temp = n; while (temp != 0) { reverse = (reverse * 10) + (temp % 10); temp = temp / 10; } return ( reverse == n); // if it is true then it will return 1; // else if false it will return 0; } // Driver Code public static void Main( string [] args) { int n = 7007; if (checkPalindrome(n) == true ) { Console.WriteLine( "Yes" ); } else { Console.WriteLine( "No" ); } } } // This code is contributed by phasing17 |
Javascript
<script> // JavaScript program to check if a number is Palindrome // Function to check Palindrome function checkPalindrome(n) { let reverse = 0; let temp = n; while (temp != 0) { reverse = (reverse * 10) + (temp % 10); temp = Math.floor(temp / 10); } return (reverse == n); // if it is true then it will return 1; // else if false it will return 0; } // driver code let n = 7007; if (checkPalindrome(n) == 1) { document.write( "Yes" , "</br>" ); } else { document.write( "No" , "</br>" ); } // This code is contributed by shinjanpatra </script> |
Yes
Time Complexity : O(log10(n)) or O(Number of digits in a given number)
Auxiliary space : O(1) or constant
This article is compiled by Aashish Barnwal.