Find Next Palindrome

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. :stuck_out_tongue:

1 Like

Please give me code links…

#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 :slight_smile:
Hope it helps :slight_smile:

1 Like

An ideone link would have been better than posting such long code in your answer.

@prakhariitd I have added ideone link :stuck_out_tongue:

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 :slight_smile:

@rahedcs

The answer to your question is actually REALLY simple.

Firstly, we will consider three type of cases-

  1. 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 :slight_smile:

3 Likes

@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! :slight_smile:

@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 :slight_smile:

1 Like

Try it, its easy!

It is something difficult.

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

https://www.codechef.com/viewsolution/14249426

1 Like
//