Smallest Immediate Palindrome Problem in C++

Today, we will see a very interesting problem usually referred to as the next palindrome problem. The problem states that, given a positive integer, we need to find the smallest palindrome larger than the given number. For example, if 809 is given as input, then the nearest palindrome greater than this number is 818. Let us see how to approach this problem and try to solve it in c++.

Palindromes

Before starting the solution, let us understand what a palindrome is first. A palindrome is any string that has the same value even when it is reversed from right to left. Here we are dealing with integers that are palindromes, for example, 818, 1331,1001, etc.

So from the basic definition, the way to check if a given number is a palindrome is obvious. We just reverse a given number and check if it is the same as the original one.

Palindrome Program in C++

Let us see how it is done in c++:

#include<iostream> 
using namespace std; 
int main() 
{
  int num,rev=0,dig,temp;
  cin>>num; temp=num;                      //we store the original value in temporary variable to compare the original to the reversed number 
  while(num!=0) 
  { 
    dig= num%10; 
    rev=rev*10+dig; 
    num=num/10;
  }
  if(temp == rev)
  cout<<"It is a palindrome."; 
  else 
  cout<<"Not a palindrome.";
  return 0; 
}

In the above program, we take the last digit of the original number and add it to the reverse number in front. And then keep removing each digit from the original number until we get zero.

Solution

So let us now start the solution to our original problem. Let us look at two methods to approach the given problem. One, a crude method derived from the definition of the problem. Then another more optimized way to solve the problem.

Crude Method in C++ (Using Palindrome Checking):

The most obvious solution to the problem from the statement is to just increment the given number and keep checking each number until we get a palindrome. We can do this using the palindrome checking code we have just seen.

#include<iostream>
using namespace std;
int palin(int num)
{ int tmp,rev;
  while(1)
  { num++;                                 //we keep incrementing the number and check if it is a palindrome or not
    tmp=num;
    rev=0;
    while(num!=0)
    { rev=rev*10+ num%10;
      num=num/10;
    }
    if(tmp==rev)
      return tmp;
    num=tmp;
   }
}
 
int main()
{
  int num;
  cin>>num;
  num=palin(num);
  cout<<num;
  return 0;
}

As we can see this is a brute force method to solve the given problem and takes a lot of time. This is because we not only have to go through all the numbers but also reverse them using another loop. Now we will see a much more refined method.

 Optimal Method

Here,  we use the basic property of a palindrome, which is symmetry.  We all can tell if a number is a palindrome or not just by looking at it because we can check if the number is symmetric about its center.

So here, we first break the number into two halves and then try to make it a palindrome by increasing its value as least as possible.

Example

Take an example input, say 1234.

We can split it as “12” and “34”

Now the left half and right half must be equal. To make it equal we will change one of the digits, but which one do we change, left or right half? Well, according to the problem the number must be as close as possible to the given number, so we have to change the right half to change the number by a lesser amount.

First, we can add 7 to the number to make the last digit 1 to match it with the first one

We then get, “12” and “41”

Now we add 9 to this so that we get, “13” and “31”

So the palindrome we needed is 1331. Here as you can see the number of iterations is half the length of the number. So this makes this method a lot faster than the previous one.

But there are a few limiting cases here that we must keep in mind. Take 1992 as input. When we add and change the number according to the above method we end up with 2001. This is because when we changed the last digit to 1, the first digit was also 1, but as we changed the other digits the first digit was also changed due to addition. One solution for this issue is to check the output at the end and pass it through the algorithm again if it is not a palindrome.

Program

Let us see the c++ code now:

#include <iostream>
#include<vector>
#include<cmath>
#include <bits/stdc++.h>
using namespace std;
vector<int> digitiz(int num)                       //a function to convert the number into an array of digits
{ int d;
  vector<int> dig;
  while(num!=0)
  { d=num%10;
    dig.insert(dig.begin(),d);
    num=num/10;
  }
  return dig;
}
int numz(vector<int> dig)                           // a function to convert the array of digits into a number
{
  int num=0;
  int digit,i;
  for(i=0;i<dig.size();i++)
  { digit=dig[i];
    num=num*10+digit;
  }
  return num;
}
int palin(int num)
{ vector<int> dig,gid;
  int n,i;
  dig=digitiz(num);
  n=dig.size();
  if(dig.size()%2==0)                          // case for even number of digits
  {
   for(i=n-1;i>(n-2)/2;i--)
    {
      if(dig[i]==dig[n-i-1])
       continue;
      else if(dig[i]>dig[n-i-1])
       {
         if(i==n/2)
          {
            num=num+(10+dig[n-i-1]-dig[i]+1)*pow(10,n-1-i);                                //we add the required number at the required position to get 
          }                                                                                      //equal digits on both sides
          else
          {
            num=num+(10+dig[n-i-1]-dig[i])*pow(10,n-1-i);
          }
       }
      else
      {
       num=num+(dig[n-i-1]-dig[i])*pow(10,n-1-i);
      }
      dig=digitiz(num);
    }

  }
  else                                                // case for odd number of digits
  {	for(i=n-1;i>(n-1)/2;i--)                    // the loop is traversed only for half the length of the number

    {
      if(dig[i]==dig[n-i-1])
       continue;
      else if(dig[i]>dig[n-i-1])
       {
          num=num+(10+dig[n-i-1]-dig[i])*pow(10,n-1-i);
       }
      else
      num=num+(dig[n-i-1]-dig[i])*pow(10,n-1-i);
      dig=digitiz(num);
   }
 }
 num=numz(dig);
 gid=dig;
 reverse(dig.begin(),dig.end());
 if(dig == gid)                                                //if it is a palindrome we return
  return num;
 else
  return palin(num);                                           //otherwise, we run the function again with the new input
}
int main()
 {
     int n,i,in;
     int num;
     cin>>num;
     num++;
     num=palin(num);
     cout<<num<<"\n";
     return 0;
}

We can see that this is not easy to write or understand as compared to the previous code. But, in terms of performance, it is far better when compared to the previous approach as we are just trying to generate a palindrome by manipulating the digits directly and not from the numbers.

Also read: Count of palindromic substrings in a string in C++

Leave a Reply

Your email address will not be published. Required fields are marked *