Category Number_Theory

Palindrome check of an Integer without converting it to a string

Arunima Mandal Leave a comment

Note: The first idea while checking a palindrome that comes to our mind is converting the integer to a string and then reversing it. And then comparing that two strings. But that takes extra space. But if we can check without converting the integer to a string, then both time and space complexity decrease for sure.

The below code is for input -2^31 < x < 2^31.

Time complexity: O(ceil (size of the integer / 2 )). That means O(1) as constant time.
Space complexity: O(1).

#include <bits/stdc++.h>

using namespace std;

bool isPalindrome(int x)
{
    if(x<0 || (x!=0 && x%10==0)) return false;
    int num=x, reverted_num_half=0;
    while(reverted_num_half < num)
    {
        int residue=num%10;
        num=num/10;
        reverted_num_half=(reverted_num_half*10)+residue;
    }
    if(num==reverted_num_half/10 || num==reverted_num_half) return true;
    else return false;
}

int main()
{
    int x=1;
    while(x!=0)
    {
        cout << "Enter an integer" << endl;
        cin>>x;
        if(isPalindrome(x)==1) cout<<"Palindrome"<<endl;
        else cout<<"Not palindrome"<<endl;
        cout<<endl;
    }

    return 0;
}