How to find the next Palindrome using Greedy Algorithm?
Input : 99
Output : 101
import java.util.Scanner;
public class Palindrome{
int reverse(int num)
{int x,rev=0;
while(x>0)
{x=num%10;num/=10;rev=rev*10+x;}
return rev;
}
public static void main(String args[]){
Scanner input=new Scanner(System.in);
for(int i=1;;i++)
{
int a=input.nextLine();
int b=reverse(a);
if(a==b){System.out.printf("%d",b);break;}
else{a+=i;continue;}
}
}
}
1 Like
This geeksforgeeks article gives a very nice approach to your question.
But please I strongly recommend that you practice it, before moving on to the solution. 
1 Like
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
#define fill(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define mp make_pair
#define sz(x) (int)x.size()
#define F first
#define S second
#define FOR(i,a,b) for(int i = a; i<=b; ++i)
#define NFOR(i,a,b) for(int i = a; i>=b; --i)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
const ll INF = 1e18;
const ll mod = 1e9+7;
const int N = 1e6+10;
char str[1000005];
int main()
{
int t,i,j;
scanf("%i",&t);
while(t--) {
scanf("%s",str);
int lenght = strlen(str);
j = lenght;
i = -1;
while(++i <= --j) {
if(str[i] != str[j]) {
break;
}
}
if(j < i) {
/* Number is palindrome */
if(lenght & 1) {
/* odd lenght */
if(str[lenght/2] < '9'){
/* check the middle one not 9 */
str[lenght/2]++;
printf("%s\n",str);
}
else {
str[lenght/2] = '0';
i = lenght/2 - 1;
j = lenght/2 + 1;
while(i >= 0) {
if(str[i] < '9') {
str[i]++;
str[j]++;
break;
}
else {
str[i] = str[j] = '0';
}
i--;
j++;
}
if(i < 0) {
printf("1");
i = lenght;
while(--i > 0) {
printf("0");
}
printf("1\n");
}
else {
printf("%s\n",str);
}
}
}
else {
/* even lenght */
i = lenght/2 - 1;
j = lenght/2;
while(i >= 0) {
if(str[i] < '9') {
str[i]++;
str[j]++;
break;
}
else {
str[i] = str[j] = '0';
}
i--;
j++;
}
if(i < 0) {
printf("1");
i = lenght;
while(--i > 0) {
printf("0");
}
printf("1\n");
}
else {
printf("%s\n",str);
}
}
}
else {
if(lenght & 1) {
i = lenght/2 - 1;
j = lenght/2 + 1;
}
else {
i =lenght/2 - 1;
j = lenght/2;
}
int flag;
while(i >= 0) {
if(str[i] - str[j] > 0) {
flag = 1;
break;
}
else if( str[i] - str[j] < 0 ) {
flag = 2;
break;
}
i--;
j++;
}
if(lenght & 1) {
i = lenght/2 - 1;
j = lenght/2 + 1;
}
else {
i = lenght/2 - 1;
j = lenght/2;
}
if(flag == 1) { /* line 1*/
while(i >= 0) {
str[j] = str[i];
i--;
j++;
}
}
else if(flag == 2 && lenght&1 && str[lenght/2] < '9'){ /* line 2*/
str[lenght/2]++;
i = lenght/2 - 1;
j = lenght/2 + 1;
while(i >= 0) {
str[j] = str[i];
i--;
j++;
}
}
else { /* line 3 */
if( lenght & 1) {
str[lenght/2] = '0';
}
while(i >= 0) {
if(str[i] < '9') {
str[i]++;
str[j] = str[i];
break;
}
else {
str[i] = str[j] = '0';
}
i--;
j++;
}
while(i >= 0) {
str[j] = str[i];
i--;
j++;
}
}
printf("%s\n",str);
}
}
return 0;
}
You can refer to this solution, it is pretty simple to understand 
Hope it helps
1 Like
@rahedcs
The answer to your question is actually REALLY simple.
Firstly, we will consider three type of cases-
- Input number is palindrome consisting of only '9’s (Eg- 99, 999, 9999 etc). In this case, its easy to see that the next palindrome is -
NextSmallesPalindrome = n+2.
//99+2=101
//999+2=1001
...and so on
2 . Next comes Input type which is a general palindrome number . Eg 1331, 121,12321,123321 etc.
For here, we can do easily see that-
a Incase the digit of number is odd, the middle digit is incremented by 1. I.e. 121==>131 , 12321==>12421. Its because middle digit will not affect the palindrome property, and we can easily prove that if any other digit except middle digit is increased, we wont get the smallest palindrome.
Meaning, in 12321, if I decide to increase 2 at second last position, I will have to increase at 2nd position too. i.e. 12321==>13331. It is NOT the smallest possible palindrome. Take some time and think over it, that increasing middle digit will yield palindrome.
Note- CORNER CASE
In case the middle digit is ‘9’, make it 0 and propagate carry to both sides of the number.
Eg- 12921==>13031. (9+1=10. ==>carry taken on left and right of it. Numbers left and right to it are 2 and 2. So they become 2+1 = 3.)
14941==>15051 and so on.
b. If the number is even, then above is followed, but for the 2 middle digits. Eg, 1331 ==>1441, 123321==>124421. If you understood for above, its not hard to apply it here as well.
Now third category, if the number is not palindrome, but a general number. Eg- 1234567.
For this I will really request you to read here because it is VERY NEATLY explained, and I don’t think that I could explain it any better. They also have provided a sample code, so do have a look!
Hope that solved the query, get back to me in case of any doubt/discrepancy
5 Likes
Try it, its easy!
Please someone help and upvote so that i can ask a qustion.
I don’t know why it is giving wrong answer. i tried it with many test cases but i still can’t point out the issue. Problem iink and my solution link are:
https://www.codechef.com/problems/PALIN
1 Like
Please give me code links…
An ideone link would have been better than posting such long code in your answer.
The code isn’t actually THAT long. The problem is extra spacing after every line which makes it tedious. @bhusan_, I think if you can edit you code to remove spaces, then it’d be really generous of you dear 
@vijju123 I have removed some of the extra space, I am too finding it tedious even after that, the code on ideone looks better.
Thanks dear, its much, MUCH better ^_^. Thanks again!
@vijju123, Bro I seriously wait for your answer on every question that requires some help. You are really making a difference here by writing quality answers. You seriously need to start making a blog or a tutorial series explaining every important questions solved by you…
1 Like
@aniketsandhya, thanks dear, I REALLY appreciate your kind words :). I will create a blog, but not now. I am still a rookie atm. Once I get a few more concepts here and there I will surely. Thanks for your comment again, you made my day
2 Likes
It is something difficult.
@vijju123 will you please provide the blog if you have written or share the material from where you have prepared or if you have notes please provide us, it will be helpful. I am putting lot of efforts, still not able to figure out where am I going wrong.
Because of last Sunday’s 2 rated contests my rating fall down like anything upon my bad performance.
Still I am not giving up on it, using practice practice practice practice practice practice mantra only. It is not working, please help me 
Pm/mail me the ids you use ( not only codechef). I feel you need more specific advice.
2 Likes
please can point out mistake its showing nzec error my code is here-
https://www.codechef.com/viewsolution/30442783