Next Palindrome
National Olympiad — Regional round
Submission name: palindrome.cpp
Problem summary
Find the smallest decimal palindrome strictly greater than N.
Input
One integer N.
Output
The next larger palindrome.
Constraints
1 ≤ N ≤ 10¹³⁰⁰.
Worked example
An independently prepared example for this explanation.
Input
1299
Output
1331
Solution analysis
- Mirror the left half onto the right. If the result exceeds N, it is the answer.
- Otherwise increment the middle position, carrying toward the left, and mirror again. An all-nine input needs one additional digit.
Why it works
A palindrome is completely determined by its left half including the center. Mirroring keeps that prefix minimal; if it is insufficient, increasing the prefix by one yields the next possible palindrome.
Complexity: O(number of digits) time and space.
Watch out. Already-palindromic inputs still require a strictly larger result.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: A palindrome is completely determined by its left half including the center. Mirroring
// keeps that prefix minimal; if it is insufficient, increasing the prefix by one yields the next
// possible palindrome.
#include<iostream>
#include<string>
#include<iterator>
using namespace std;
int main(){
string s;
cin>>s;
string a=s;
int n=a.size();
for(int i=0;i<n/2;i++){
a[n-1-i]=a[i];
}
if(a<=s){
int i=(n-1)/2;
while(i>=0&&a[i]=='9'){
a[i--]='0';
}
if(i<0){
cout<<'1'<<string(n-1,'0')<<"1\n";
return 0;
}
a[i]++;
for(int j=0;j<n/2;j++){
a[n-1-j]=a[j];
}
}
cout<<a<<'\n';
}