Given a number N, our task is to find the closest Palindrome number whose absolute difference with given number is minimum. If 2 Palindome numbers have same absolute difference from the given number, then output the smaller one.
For each test case, the print the closest palindrome number.
Note: If the difference of two closest palindromes numbers is equal then we print smaller number as output.
For Input: 5 848 1001 500999 1756183123 815901158 Your Output is: 848 1001 501105 1756226571 815898518
#include <bits/stdc++.h>
using namespace std;
long long int palindrome(long long int n)
{
long long int pre=n;
vector<int> v;
//just spliting number into digits
while(n>0)
{
v.push_back(n%10);
n/=10;
}
//vector stored digits in reverse order
int i=0,j=v.size()-1;
//so we have taking mirror of leftside
while(i<=j)
{
if(v[i]!=v[j])
v[i]=v[j];
++i,--j;
}
long int a=0,b=0,c=0;
//
for(i=0;i<v.size();++i)
a=a*10+v[i];
// if given is palindrome return itself
if(pre==a)
return pre;
// checking length of size of vector
if(v.size()%2==1)
{
//if it is odd
//compare with actual value
if(a<pre)
{
// if a less than actual then just add 1 to middle if it is not 9
// if it is 9 then on adding 1 become 10 so add to left of middle
//making that mirror to right of middle
if(v[v.size()/2]==9)
{
v[v.size()/2-1]+=1;
v[v.size()/2]=0;
v[v.size()/2+1]=v[v.size()/2-1];
}else{
v[v.size()/2]+=1;
}
}
else
{
// if a greater than actual then just substruct 1 to middle
// if middle is greater than 0
// if middle is 0 then substruct to left of middle
// and in middle place 9 and right of middle is mirror of left
if(v[v.size()/2]==0)
{
v[v.size()/2-1]-=1;
v[v.size()/2]=9;
v[v.size()/2+1]=v[v.size()/2-1];
}else{
v[v.size()/2]-=1;
}
}
//calculating the possible nearest palindrome number
for(i=0;i<v.size();++i)
b=b*10+v[i];
// if equal distance from actual number then return smallest number
// else return small distance palindrome
if(abs(a-pre)==abs(b-pre))
{
return min(a,b);
}else if(abs(a-pre)<abs(b-pre))
{
return a;
}else{
return b;
}
}else{
//if length is even
//we have add 1 and substract to middle element
//to genarate two palindrome
// one left and one right of 'a' number
for(i=0;i<v.size();++i)
{
if((i==v.size()/2)||(i==(v.size()/2-1)))
{
if(v[i]<=9)
c=c*10+v[i]-1;
if(v[i]>=0)
b=b*10+v[i]+1;
}else{
b=b*10+v[i];
c=c*10+v[i];
}
}
//compare and finding small distance palindrome number
if(abs(a-pre)<abs(b-pre)&&abs(c-pre)>abs(a-pre))
{
return a;
}else
if(abs(a-pre)>abs(b-pre)&&abs(c-pre)>abs(b-pre))
{
return b;
}else if(abs(a-pre)>abs(c-pre)&&abs(c-pre)<abs(b-pre))
{
return c;
}
}
return a;
}
int main() {
//code
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
if(n<10)
{
cout<<n<<endl;
}else{
cout<<palindrome(n)<<endl;
}
}
return 0;
}
