Program to check whether a number is a Palindrome or not

Approach 1 

Intuition for the solution lies in the definition of palindrome itself, 'when a number is reversed,' we will reverse the given number and compare it with the original one.

If both the numbers remain equal, for example, 121, when reversed, gives 121, the given number is a palindrome. Otherwise, the number is not a palindrome.

Logic

To check if the number is a palindrome or not, we need to calculate the reverse of the number to compare it with the original number.

Step 1: We initialize a copy of the original number in the copy_num variable.

Step 2: We initialize the rev variable as zero for storing our reversed number.

Step 3: We start a while loop with the condition to iterate until our copy_num variable is not zero.

Step 4: Inside the loop, we calculate the most insignificant digit through modulo 10. 

Step 5: We will update the rev as rev*10 + digit.

Step 6: We will update the copy_num number as copy_num/10 for removing the most insignificant number we just transferred to rev.

Step 7: End while loop

Step 8: We will compare if the rev equals the original number, num, then we say the number is a palindrome. Otherwise, the number is not a palindrome.

Code 

#include <iostream>
using namespace std;
int main()
{
    int num, copy_num, digit, reversed = 0;
     cout << "Enter a positive number: ";
     cin >> num;
     copy_num = num;

     do
     {
         digit = copy_num % 10;
         reversed = (reversed * 10) + digit;
         copy_num = copy_num / 10;
     } while (copy_num != 0);

     if (num == reversed)
         cout << "The number is a palindrome.";
     else
         cout << "The number is not a palindrome.";

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Enter a positive number: 52
The number is not a palindrome.

Enter a positive number: 525
The number is a palindrome.

You practice by yourself with the help of online c++ compiler.

Time Complexity

The time complexity of the above approach to checking whether the number is a palindrome is O(d), where d is the number of digits or O(log₁₀(n)), where n is the number itself.

Space complexity

Since no space is used, the space complexity of the above approach to checking whether the number is a palindrome is O(1).

Read More - Time Complexity of Sorting Algorithms

Approach 2

We can check whether the number is a palindrome or not by checking the digit of a number from starting and end until we reach the middle. There are two further types of approaches to check the first and the last digits of a number.    

Also read -  Decimal to Binary c++

Recursive Solution

The aim is to make a copy of num and pass the copy by reference while passing num by value recursively. Divide num by 10 as you move down the recursion tree in the recursive calls. Divide the copy by 10 as you progress up the recursion tree. The last digit of num will be an ith digit from the beginning, and the last digit of copy will be an ith digit from the end when they meet in a function for which all child calls have been completed.

Code

#include <iostream>
using namespace std;

// Check if the num has only one digit
int isOneDigit(int num)
{
    return (num >= 0 && num / 10 == 0);
}

bool isPalUtil(int num, int *copyNum)
{

    // Base case, compares the first digit and the last digit
    if (isOneDigit(num))
        return (num == (*copyNum) % 10);

    // Although each recursive call has its own copy of num, they all share the same copy of *dupNum.
    // As we progress up the recursion tree, we split num.
    if (!isPalUtil(num / 10, copyNum))
        return false;

    // Dividing the copyNum by 10 when we move up the recursion call tree
    *copyNum /= 10;

    // At last, check the num%10,
    // i'th digit from beginning,
    // with (*dupNum)%10, i'th digit
    // from end
    return (num % 10 == (*copyNum) % 10);
}

int isPal(int num)
{

    // Make the integer positive
    num = abs(num);

    // Create a separate copy of num,
    int *copyNum = new int(num);

    return isPalUtil(num, copyNum);
}

int main()
{
    int n;
    cout << "Enter the number: ";
    cin >> n;
    cout << "The number is ";
    isPal(n) ? cout << "a palindrome\n" : cout << "not a palindrome" << endl;
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Enter the number: 1221
The number is a palindrome

Enter the number: 22321
The number is not a palindrome

Time Complexity

The time complexity of the above approach to checking whether the number is a palindrome is O(log(n)), where n is the number.

Space complexity

The space complexity of the above approach to checking whether the number is a palindrome is O(log(n)), for using n call stacks.

Must Read  C Program to Reverse a Number.

Iterative Solution

The aim is to find the appropriate divisor that can divide the given number till the second most significant number and then extract and compare the digits from starting and ending until we reach the middle. We will use two while loops, first to find the number of digits present in the number and second for the digits' actual comparison.

Code

#include <bits/stdc++.h>
using namespace std;
bool isPalindrome(int);

bool isPalindrome(int num)
{
    // Find divisor
    int divv = 1;
    while (num / divv >= 10)
        divv *= 10;

    while (num != 0)
    {
        int significant = num / divv;
        int insignificant = num % 10;

        // Compare the first and last digits
        if (significant != insignificant)
            return false;

        // Removing the significant and insignificant digits after comparing
        num = (num % divv) / 10;

        // Reducing divisor by a factor
        // of 2 bacause 2 digits are dropped
        divv = divv / 100;
    }
    return true;
}

// Driver code
int main()
{
    int n;
    cout << "Enter the number: ";
    cin >> n;
    cout << "The number is ";
    isPalindrome(n) ? cout << "a palindrome\n" : cout << "not a palindrome" << endl;
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Enter the number: 455
The number is not a palindrome

Enter the number: 1221
The number is a palindrome

Time Complexity

The time complexity of the above approach to checking whether the number is a palindrome is O(d), where d is the number of digits or O(log₁₀(n)), where n is the number itself.

Space complexity

Since no space is used, the space complexity of the above approach to checking whether the number is a palindrome is O(1).

You can also read about Palindrome Number in Python here.

FAQs

1. How can we reverse a number using STL functions?
   In C++, first convert the number into string using toString() function and using reverse(s.begin(), s.end()) STL function, we can reverse the string. Finally, using the atoi() function, we can convert the string back to an integer.
    
2. What other approach can we follow to check if a number is a palindrome?
   Another approach for checking whether the number is a palindrome or not is converting the given number into a string and then checking each element from start and end positions using two pointers (incrementing and decrementing at each step, respectively, until they cross each other). If they appear unequal at any iteration, then the number is not a palindrome. Otherwise, the number is a palindrome if the loop successfully terminates.

Key Takeaways

This article extensively discussed the most common approaches to checking whether the number is a palindrome.

We hope this blog has helped you enhance your knowledge. For learning more about coding in C++ or other problems like the Program To Print All Permutations Of A Given String or find the factorial of a number, check out Code Studio's blog site.

Check out this problem - Reverse Nodes In K Group

Related articles:

• Reverse A String In C