Find the next palindrome

Question

Given a number, I am trying to find the smallest palindrome number greater than given number. Here is my code:

#include<bits/stdc++.h>
using namespace std;
char a[1000005];
int main(){
    int t,len,ni,nj,nk,i,j,k;
    cin>>t;
    while(t--){
        cin>>a;
        char ch=getchar();
        len=strlen(a);
        k=len-1;
        for(i=0;i<len;i++){
            if(a[i]!='9'){
                break;
            }
        }
        if(i==len){                         //if all digits are 9
            for(i=len-1;i>0;i--){
                a[i]='0';
            }
            a[0]='1';
            a[len]='1';
            a[len+1]='\0';
        }
        else{
            for(i=0;i<len/2;i++){
                if(a[i]!=a[len-1-i]){               //check if number is already palindrome
                    break;
                }
            }
            if(i==len/2){                           //add 1 if it is already palindrome
                j=len-1;
                while(1){
                    nj=((int)a[j])-48;
                    nj++;
                    if(nj<10){
                        a[j]=nj+48;
                        break;
                    }
                    else{
                        a[j]=48;
                        j--;
                    }
                }
            }
            for(i=0;i<len/2;i++){
                if(a[i]==a[k]){                 //compare first with last,second with second last...
                    k--;
                }
                else{
                    nk=((int)a[k])-48;
                    ni=((int)a[i])-48;
                    if(nk<ni){

                        a[k]=ni+48;

                    }
                    else{
                        j=k;    a[j]=ni+48; j--;
                        while(1){
                            nj=((int)a[j])-48;
                            nj++;
                            if(nj<10){
                                a[j]=nj+48;
                                break;
                            }
                            else{
                                a[j]=48;
                                j--;
                            }
                        }
                        if(j<=i){
                            i=j-1;
                            k=len-j;
                        }
                    }
                    k--;
                }
            }
            if(len%2==0){
                a[len/2]=a[len/2-1];
            }
        }
        cout<<a<<endl;
    }
    return 0;
}

My code is working fine for all the inputs I have tried, but it is not getting accepted. Is my code right?

That's a lot of code for such a simple task, you should most likely think about another approach. And **don't** include `stdc++` (http://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h). Actually that might even be the reason why it's not accepted, if it's working. And more meaningful variable-names would make this a lot simpler to understand. — , Jan 31 '16 at 20:21
It is showing WA. Problem is http://www.spoj.com/problems/PALIN/ — Vivek Mangal, Feb 01 '16 at 12:14
Finally got accepted. I removed explicit type casting in my code as they were unnecessary and directly compared the array elements. Perhaps, this was the problem. Thanks for the answers. — Vivek Mangal, Feb 01 '16 at 13:18

score 1 · Answer 1 · edited May 23 '17 at 11:59

Some of the reasons why this code might have been rejected are:

length of code: finding the smallest palindromic number greater than a given input can be done with a lot less code.
memory efficiency: ~1MB of memory is by far too much for operations that can easily be done in-place. The total memory required would simply be the size of the number plus a few additional integer-vars.
runtime efficiency: This problem could be solved in O(n), where n is the number of digits of the number. I don't quite get the way your code works - and to be honest I won't put any effort in understanding that mess -, but that doesn't exactly look linear (or even close to it).
#include <bits/stdc++.h>: This header is GNU-specific, compiler-specific, ... . This code might not even compile if the tester uses another compiler. Apart from that the compilation takes more time with this header and will produce a larger executable than if you'd simply include the required headers. The reasons why it's a bad idea to use this header are described here in a more extensive way.

I can only speculate about the reason(s) why the solution really was rejected. The least information required to answer this would be a link to the judge that rejected it - which should aswell give a reason why it was rejected.

The reasons you have mentioned don't matter. 1. Length of code is not that much, it is well under the file size limit. 2. As the code suggests, the number input is not an integer but a String, which user has input as char[], ie. number of digits in input must be around 10^6. 3. Runtime efficiency of his solution is O(n). See for yourself. 4. There are many reasons not to include this header file but I have got many of my solutions accepted on many online judges with this, before I learnt its downsides. — vish4071, Feb 01 '16 at 08:19
@vish4071 As I already said at the end: this are only **speculations**. OP didn't even provide a link to the judge or the task itself, thus these are only guesses. As for point 2, just the same problem with OPs question: too little information, it's just a **guess**. point 3: yeah, you're right. I just got a little bit confused with that mess of variables and loops. point 4: that depends upon judges policy and it's compiler, just as I said. — , Feb 01 '16 at 10:20
Finally got accepted. I removed explicit type casting in my code as they were unnecessary and directly compared the array elements. Perhaps, this was the problem. Thanks for the answers. — Vivek Mangal, Feb 01 '16 at 13:16

Find the next palindrome

1 Answers1