http://www.geeksforgeeks.org/given-a-number-find-next-smallest-palindrome-larger-than-this-number/
Given a number, find the next smallest palindrome
#include <iostream>
#include <vector>
using namespace std;
int toNumber(vector<int> intArray)
{
int res = 0;
for(int i=0;i<intArray.size();i++)
{
res = res*10;
res+= intArray[i];
}
return res;
}
bool containAllNines(vector<int> intArray)
{
for(int i=0;i<intArray.size();i++)
{
if(intArray[i]!=9)
{
return false;
}
}
return true;
}
int findNextPalindrome(int n)
{
vector<int> intArray;
int temp = n;
while(temp)
{
intArray.push_back(temp%10);
temp/=10;
}
reverse(intArray.begin(), intArray.end());
if(n<9)
{
return n+1;
}
//case 1
if(containAllNines(intArray))
{
return n+2;
}
//case to check if we need to add +1 to the middle digits of the number or not
int mid = (int)intArray.size()/2;
int i = mid-1;
int j = intArray.size()%2?mid+1:mid;
bool incrementNeeded = false;
while(intArray[i]==intArray[j])
{
i--;
j++;
}
if(i<0 || intArray[i]<intArray[j])
{
incrementNeeded = true;
}
while(i>-1 && j<intArray.size())
{
intArray[j++] = intArray[i--];
}
if(incrementNeeded==true)
{
i = mid-1;
int carry = 1;
if(intArray.size()%2)
{
intArray[mid] += carry;
carry = intArray[mid]/10;
intArray[mid] %= 10;
j = mid+1;
}
else
{
j = mid;
}
//propogate the carry till the Least significant bit of the number
while(i>-1 && j<intArray.size())
{
intArray[i] += carry;
carry = intArray[i]/10;
intArray[i] %= 10;
intArray[j++] = intArray[i--];
}
}
int res = toNumber(intArray);
return res;
}
int main(int argc, const char * argv[]) {
// insert code here...
int n;
cin>>n;
cout<<"next palindrome is"<<findNextPalindrome(n);
return 0;
}
No comments:
Post a Comment